摘要：
每个点只能走一次。该问题被转换为与P1004网格相同的情况，即从左上角到右下角有两条不同的路径，使用namespacestd删除重复的点#include˃m˃˃n；对于｛for｛cin˃˃v1；a[i][j]=v1；｝｝对于｛for{dp[i][j][k][l]=max+a[i][j]+a[k][l]；ifdp[i][j][k][l]-=a[i][i][j]；//如果同一点被添加两次，则一个｝｝｝｛cout˂˂dp[m][n][n][n]˂endl；return0；｝视图代码
题意是两条路径一条左上角到右下角、一条从右下角到左上角，找权值最大的两条路径。每个点只能走一次。
问题转化为和P1004方格取数一样的情形，即两条不同的路径从左上角到右下角，并去掉重复加的点即可。
#include<bits/stdc++.h> using namespace std; const int maxn=55; int dp[maxn][maxn][maxn][maxn]; int a[maxn][maxn]; int m,n,v1,v2,v3; int main() { cin>>m>>n; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ cin>>v1; a[i][j]=v1; } } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ for(int k=1;k<=m;k++){ for(int l=1;l<=n;l++){ dp[i][j][k][l]=max(dp[i-1][j][k-1][l],max(dp[i-1][j][k][l-1],max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])))+a[i][j]+a[k][l]; if(i==k&&j==l)dp[i][j][k][l]-=a[i][j];//如果同一个点加了两次必须减掉一个 } } } } cout<<dp[m][n][m][n]<<endl; return 0; }