Vijos 1235 天堂的馈赠 解题报告

囧……这题再次让我对我的题目理解能力无语……并且在为了理解题意看题解的过程中不小心看到了某些同学的善意提醒，于是在不知道数据已经修正的情况下白白贡献了一次WA……

理解了题意后DP就很容易想到了，首先先解释一下不可能得到的礼物是指以下两种情况：1、v不能被h整除（也就是不能在整秒末落在格子上）；2、从一开始就从最初的位置向该位置移动也无法接到。

于是在预处理时就可以求出第二问的答案，同时用c[i,j]记录下第i秒在第j个格可以获得礼物价值总和，用tmax记录下可得到的礼物的最大的落下时间。则可以得到DP的状态转移方程：f[i,j]=max(f[i-1,j-1],f[i-1,j],f[i-1,j+1])+c[i,j](1<=i<=tmax,1<=j<=w)。由于f[i]只与f[i-1]有关，因此可以用滚动数组优化，但由于c数组无法使用这一优化，因此空间复杂度并没有降低，只是常数低了罢了。

R1123984 Accepted 100 From IwfWcf－ P1235 FPC Vijos Dolphin 2009-1-26 21:37:56