题目链接http://noi.openjudge.cn/ch0206/8786/
描述
设有N*N的方格图(N<=10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）：< p="">
某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。 此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
输入输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。输出只需输出一个整数，表示2条路径上取得的最大的和。样例输入
82 3 132 6 63 5 74 4 145 2 21 5 6 46 3 157 2 140 0 0
样例输出
67
来源NOIP2000复赛 提高组 第四题
（WA）原来想先取一次最优解，更新后，再去一次最优解。发现过不了。这是一种贪心，这两个局部最优解不一定是整体最优解。可能两个局部最优解不可能把整个带数的格子取完，但整体最优解可以。
(AC) 后来查了一下，发现这个是一个多线程DP，同时模拟两个人走。
dp[i][j][k][r]表示第一个人走到(i,j)，第二个人走到(k,r)的最优解。其可由max(dp[i-1][j][k-1][r]，dp[i][j-1][k][r-1])，dp[i][j-1][k-1][r]，max(dp[i-1][j][k][r-1]) + {maps[i][j]（两个人位置重合时）或 maps[i][j]+maps[k][r]（两个人位置不重合时）}转移而来。
WA：
#include#include #include #include #include #include #include #define DEBUG(x) cout<<#x<<" = "< < Len[i][j+1])dfs(i+1,j,l-Matrix[i][j]); else dfs(i,j+1,l-Matrix[i][j]); if(Len[i][j]==l&&Matrix[i][j]!=0){ Matrix[i][j]=0; }}int main(){ scanf("%d",&N); int ans=0; while(true){ int i,j,v; scanf("%d%d%d",&i,&j,&v); if(i==0)break; Matrix[i][j]=v; } Len[N][N]=Matrix[N][N]; for(int k=N-1;k>=1 ;k-- ){ Len[N][k]+=Len[N][k+1]; Len[k][N]+=Len[k+1][N]; } for(int i=N-1;i>=1 ;i-- ){ for(int j=N-1;j>=1 ;j-- ){ Len[i][j]=max(Len[i][j+1],Len[i+1][j])+Matrix[i][j]; } } dfs(1,1,Len[1][1]); ans=Len[1][1]; memset(Len,0,sizeof(Len)); Len[N][N]=Matrix[N][N]; for(int k=N-1;k>=1 ;k-- ){ Len[N][k]+=Len[N][k+1]; Len[k][N]+=Len[k+1][N]; } for(int i=N-1;i>=1 ;i-- ){ for(int j=N-1;j>=1 ;j-- ){ Len[i][j]=max(Len[i][j+1],Len[i+1][j])+Matrix[i][j]; } } ans+=Len[1][1]; printf("%d\n",ans);}
AC：
#include#include #include #include #include #include #include #define DEBUG(x) cout<<#x<<" = "< <
还有一个问题比较迷，为什么是从这四个状态转移过来的dp[i-1][j][k-1][r]，dp[i][j-1][k][r-1])，dp[i][j-1][k-1][r]，max(dp[i-1][j][k][r-1]？
参考文献
https://blog.csdn.net/heyanbai/article/details/79519532