显然,定义状态f[i][j][k][l]表示第一条路线走到(i,j),第二条走到(k,l)所取的数最大和。
状态转移方程即f[i][j][k][l]= max( max(f[i-1][j][k-1][l],f[i][j-1][k-1][l]), max(f[i-1][j][k][l-1],f[i][j-1][k][l-1]) )+a[i][j]+a[k][l];
当然,若(i,j)与(k,l)重合,只需要减掉一个即可。
本题还存在空间复杂度更优的算法,但此算法足够通过本题,本人很懒……
1 #include<bits/stdc++.h> 2 using namespace std; 3 int ans[51][51][51][51],a[51][51],n,m; 4 int main() 5 { 6 scanf("%d%d",&n,&m); 7 for(int i=1;i<=n;i++) 8 for(int j=1;j<=m;j++) 9 { 10 scanf("%d",&a[i][j]); 11 } 12 for(int i=1;i<=n;i++) 13 for(int j=1;j<=m;j++) 14 for(int k=1;k<=n;k++) 15 for(int l=1;l<=m;l++) 16 { 17 ans[i][j][k][l]= 18 max( 19 max(ans[i-1][j][k-1][l],ans[i][j-1][k-1][l]), 20 max(ans[i-1][j][k][l-1],ans[i][j-1][k][l-1]) 21 )+a[i][j]+a[k][l]; 22 if(i==k&&j==l) ans[i][j][k][l]-=a[i][j]; 23 } 24 printf("%d",ans[n][m][n][m]); 25 return 0; 26 }