Vijos 1006 晴天小猪历险记之Hill 解题报告

模型是很经典的三角形取数DP。对于这种可以从两边取数的题目，只需要从左往右和从右往左分别扫一次即可保证最优解。显然一行之中最少有一个数的最优解是从下一行直接得到的，因此这样扫两次可以看作是以这一最优解为中心向两边扫。必须交需要注意的是看懂题目，对于边界的特殊处理，简单来说就是看成一个环，不过边界的处理独立写一下就是了，没必要像一般的环形DP那样复制多一次。还要需要注意的就是因为这题边界处理的特殊情况，从左往右扫时应该从最后一个开始扫，从右往左扫时应该从第一个开始扫。

状态转移方程是f[i,j]=max(f[i+1,j],f[i+1,j+1],f[i,j-1],f[i,j+1])+map[i,j]，由于是具有环形质的DP，实现的方法和一般的线性DP有点不同（见上文）。

R1074083 Accepted 100 From IwfWcf P1006 FPC Vivid Puppy 2008-11-22 23:45:07