以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『 算法理论与分析 』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  谁能告诉我双重DP怎么实现？  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=29539)

--  作者：huyichen
--  发布时间：3/29/2006 10:37:00 PM

--  谁能告诉我双重DP怎么实现？
谁能告诉我双重DP怎么实现？
--  作者：Logician
--  发布时间：3/30/2006 3:11:00 AM

--  
你要拿个具体的例子来吧？
这样怎么说呢？
--  作者：huyichen
--  发布时间：3/30/2006 4:54:00 PM

--  
山用一个三角形表示，从山顶依次向下有1段、2段、3段等山路，每一段用一个数字T（1<=T<=100）表示，代表晴天小猪在这一段山路上需要爬的时间，每一次它都可以朝左、右、左上、右上四个方向走（**注意**：在任意一层的第一段也可以走到本层的最后一段或上一层的最后一段）。
　　晴天小猪从山的左下角出发，目的地为山顶，即隐者的小屋。
第一行有一个数n（2<=n<=1000），表示山的高度。
　　从第二行至第n+1行，第i+1行有i个数，每个数表示晴天小猪在这一段山路上需要爬的时间。
 　一个数，即晴天小猪所需要的最短时间。
Input
5
1
2 3
4 5 6
10 1 7 8
1 1 4 5 6

Output
10

--  作者：phoenixinter
--  发布时间：3/30/2006 6:43:00 PM

--  
spfa....
--  作者：huyichen
--  发布时间：3/30/2006 7:08:00 PM

--  
我只想知道用DP的方法
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 46.875ms