新世界

SRM 208 DIV1 的level 3，题意是给一个张网，每个给子里有一定量的苹果，求然后有三个人从左上角走到右下角，每个人走过一个格子的时候就会把当前格子里的苹果都带走，问三个人能拿到的最多的苹果是多少。

很显然的一个解法dp，dp[step][i][j][k]，意义是走完step步，第一个人在(i,step-i)，第二个人在(j,step-j)，第三人在(k,step-k)的时候能拿到的最多苹果是多少。

这题还有另一种解法，是要观察出一个性质，就是三条路径除了第一行和最后一行，路径不会相交，就是说可以理解成从第一行连到最后一行的三条路，路径不相交，相交肯定不是最优的，这个比较容易证明。然后是dp的时候怎么能体现出这个三条路径不相交的性质来。dp[row][i][j][k]为第row行，当前三条路径终点在(row,i)，(row,j)，(row,k)三个点时能拿到的最多苹果，那么此时可以枚举上一行的状态，也即dp[row-1][pi][pj][pk]，然后转移状态，但是这样的复杂度过高，所以只能另寻他法。其实dp[row][i][j][k]可以由当前行的状态转移过来，如dp[row][i-1][j][k]等转移来，意义就是从(row,i-1,j,k)向右走一步过来。但是这里要注意状态转移的顺序，开始我是这么写的

FOR(i,0,cols)FOR(j,i+1,cols)FOR(k,j+1,cols){
    if(i>0)dp[row][i][j][k] = max(dp[row][i-1][j][k]+apple[row][i], dp[row][i][j][k]);
    ...
}

但是这样是完全不对的，因为这样根本没有考虑转移顺序的问题，这样转移出来的路径是有交叉的。正确的应该像这样

FOR(i,0,cols)FOR(j,i+2,cols)FOR(k,j+1,cols)     ...(A)
    dp[row][i][j][k] = max(dp[row][i][j][k], dp[row][i-1][j][k]+apple[row][i]);

FOR(i,0,cols)FOR(j,i+1,cols)FOR(k,j+2,cols)     ...(B)
    ...

FOR(i,0,cols)FOR(j,i+1,cols)FOR(k,j+1,cols-1)   ...(C)
    ...

这样转移出来的路径是绝对不会交叉的，原因就是，这样得到的dp[row][i][j][k]是(C)得来的，(C)由(B)得来，(B)由(A)得来，而每个式子得来的时候，都会保证路径是不相交的。所以最后的结果路径是不相交的，简单点说就是让最左边的路往右走一步，对每个(j,k)都处理完的时候，再走中间的路。好好想想...