这个题开始我想的时候不允许点重合，因此错了，事实上当然可以，只不过我们每个点只能记录一次答案就好……
我们可以换一种方式理解这个题，我们假设其实起点有两个人一起向终点走去（因为显然路径可以反向走），这样就好处理多了
#include<iostream> #include<cstdio> using namespace std; int n,m; int mmp[55][55],dp[55][55][55][55];//dp[i][j][k][l]表示a走到(i,j) ,b走到(k,l)的时候的答案 int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&mmp[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=n;k++) for(int l=1;l<=m;l++) { dp[i][j][k][l]=max(dp[i-1][j][k-1][l],max(dp[i][j-1][k-1][l],max(dp[i-1][j][k][l-1],dp[i][j-1][k][l-1])))+mmp[i][j]+mmp[k][l];//两个人各有两种方法向现在的状态转移，合起来就是2*2=4种 if(i==k&&j==l)//允许在同一个点上，但是这个点只会记录一次 dp[i][j][k][l]-=mmp[i][j]; } printf("%d",dp[n][m][n][m]); }
原文：http://www.cnblogs.com/Loi-dfkdsmbd/p/7754927.html