Vijos 1143 三取方格数 解题报告

本题的状态转移方程的推导思路和Vijos 1014非常类似，题目所求路径可以看到三个人同时从左上角走n+n-1步到右下角的路径，显然最优路径应该是除了起点和终点外没有重复走过的路径。为了降低时间复杂度和空间复杂度，第i步所处的坐标(j,k)可以用(j,i-j+1)表示，这样时间复杂度和空间复杂度就可以降到O(n^4)，在题目的数据范围内是可以承受的了。因此上述限制可以转化为在走了同样步数后，三人所处行不能相同。

状态转移方程是f[t,i,j,k]=max(f[t-1,i-1,j,k],f[t-1,i,j-1,k],f[t-1,i,j,k-1],f[t-1,i-1,j-1,k],f[t-1,i-1,j,k-1],f[t-1,i,j-1,k-1],f[t-1,i-1,j-1,k-1])+map[i,t-i+1]+map[j,t-j+1]+map[k,t-j+1];(t-n+1<=i<=t,t-n+1<=j<=t,t-n+1<=k<=t)。由于f[t]只与f[t-1]有关，所以可以用滚动数组降低空间复杂度为O(n^3)。

PS：本题是NOIP2000 方格取数也即NOIP2008 传纸条的加强版，话说我NOIP2008就是挂在了这题上面......

R1071659 Accepted 100 From IwfWcf P1143    FPC Vivid Puppy 2008-11-20 13:24:30