个人觉得把这题归在DP里面不合适, 呵呵.

可以dp

更可以dijistra

ms最短路径的n(logn)的算法过的了

吐血。。。交了我四遍才AC。。。

关于本DP的一点小小心得，见笑：

最原始的方程就是三角形那个，但是在此基础上还需要一些改进。。

1.DP有环怎么办?

别急,先别想着放弃DP,有时候环是可以避免的.这里在每一行中为避免相邻两格左右移动产生的环,可以先推向左的,再推向右的,而同向移动产生的那个“大”环就麻烦一点.其实有个很简单的窍门:先记录从下一行转移来的最优值,然后在本行中寻找代价最小的点,以这个点为起点分别向左向右推,因为最小的点显然是不需要从两侧的点过来的.这样就没有后效性了..

2.递推的顺序:

递推有两种顺序,可以根据当前状态值推出所有可能的后继状态,也可以根据所有当前状态可能的前驱来推当前值,很多时候,当问题的状态比较有规律时,这两种方法是不相上下的.但是其他情况下一不小心就可能搞错.比如这题题目告诉我们的是从一个状态可行的所有走法(共四种),所以根据这个顺序去编是最保险的。因为这里一个状态的前驱不一定只是四个,边缘的点是特例,可能会有5个来源,所以DP的时候不要随便换状态转移顺序.

3.坐标的处理

我第一次把上一行的坐标全部向左移了一格..改过来之后还是错,结果发现是又漏了一个%length...在处理滚动数组的时候一定要记得检查每个下标,是不是少了取余运算!

和小胖办证太像了!

题目中的"注意......"中的内容,反之亦然

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

纪念AC50题

program P1006;

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

^0^

和数字三角形差不多,只是由下层推完上层后,上层还要横着推,更新最优值.

这个题目有点像hnoi2007省队选拔第一试第一题 海盗分宝 （只是后者难度和这个真不是一个等级的，后者太难了）。但状态转移的方法是一样的：先跨行，再在同行进行两次不同方向的动规。这道题目也和数字三角形有几分相似，跨行的状态转移可以参考前者的动规式，只是要注意 “在任意一层的第一段也可以走到本层的最后一段或上一层的最后一段” 这个条件。

这个参考数字三角和海盗分宝所得出来的动规程序，复杂度大约是O(3*n)。

xmyzxsxy

（**注意**：在任意一层的第一段也可以走到本层的最后一段或上一层的最后一段）。

这句话让我调试了一个小时……大家要注意这里，也可以从本层的最后一段走到本层的第一段或上一层的第一段。

。。。。。。。。可以到上一层？ 5555原来是这样啊

一眼看上去，不得不会让人觉得这就是传说中最经典的动态规划例题——数字三角形！可是，只要把题目仔细看完，就不难发现这和数字三角形还是有明显区别的。

1、 它能在同行走，比数字三角形单纯的两个方向更为复杂。

2、 这道题目中的等腰三角形可以看成是个左右两腰相拼合的圆锥，因为它的最左端和最右端是相通的。

只要发现了这两个明显的区别，那么只需经过仔细的思考和细心的编程，那么这道题目我想就比较容易解决了。

O(N*N)

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

从上往下推容易多了。

但要注意山两侧的点下山路径不止两条,而是三条。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

我靠，用的暴力DP竟然也过了……

郁闷那！！！

在任意一层的第一段也可以走到本层的最后一段或上一层的最后一段

这句话看都没看 晕那！！！

只有6，10ac

太不仔细了！！！

在任意一层的第一段也可以走到本层的最后一段或上一层的最后一段

...

...

终于明白这句话的作用了

就是f:=f; f:=f

恍然大悟

......................~.~

按习惯来说叫双向DP.....按原理来说叫恶搞..残念

比较容易的DP，O(n^2)

我自底而上，对于每一层首先f=min(f,f)+s

然后分别从前往后、从后往前扫一遍

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

爽啊!!!

AC99题纪念一下。

有人知道怎么不用暴力解决的DP方法啊？

暴力似乎效率不高。

双重DP　见小胖办证