https://www.luogu.org/problem/show?pid=1006#sub 和方格取数类似，可以看做同时从左上角出发，同时走，步数是同步的。 可以用四维数组，也可以用三维数组。 从左上角到右下角，步数是两点的曼哈顿距离。 得到状态转移方程 ：
int h=max(max(f[k-1][i][j],f[k-1][i-1][j]),max(max(f[k-1][i][j-1],f[k-1][i-1][j-1]),f[k][i][j])); f[k][i][j]=h+a[i][k-i+1]+a[j][k-j+1]; if(i==j) f[k][i][j]-=a[i][k-i+1];或者
if ((i1!=i2&&j1!=j2)|(i1==m&&i2==m&&j1==n&&j2==n)) { int h=max(max(dp[i1-1][j1][i2][j2-1],dp[i1][j1-1][i2-1][j2]),max(dp[i1-1][j1][i2-1][j2],dp[i1][j1-1][i2][j2-1])); dp[i1][j1][i2][j2]=h+a[i1][j1]+a[i2][j2]; if(i1==i2) dp[i1][j1][i2][j2]-=a[i1][j1]; }代码：
#include<iostream> #include<cstdio> using namespace std; int m,n; int a[55][55],f[109][55][55]; int dp[55][55][55][55]; int main() { scanf("%d%d",&m,&n); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); //三维 /*for(int k=1;k<=(n+m-1);k++) { for(int i=1;i<=min(k,m);i++) { for(int j=1;j<=min(k,m);j++) { int h=max(max(f[k-1][i][j],f[k-1][i-1][j]),max(max(f[k-1][i][j-1],f[k-1][i-1][j-1]),f[k][i][j])); f[k][i][j]=h+a[i][k-i+1]+a[j][k-j+1]; if(i==j) f[k][i][j]-=a[i][k-i+1]; } } } printf("%d",f[n+m-1][m][m]);*/ //四维 for(int i1=1;i1<=m;i1++) for(int j1=1;j1<=n;j1++) for(int i2=1;i2<=m;i2++) for(int j2=1;j2<=n;j2++) if ((i1!=i2&&j1!=j2)|(i1==m&&i2==m&&j1==n&&j2==n)) { int h=max(max(dp[i1-1][j1][i2][j2-1],dp[i1][j1-1][i2-1][j2]),max(dp[i1-1][j1][i2-1][j2],dp[i1][j1-1][i2][j2-1])); dp[i1][j1][i2][j2]=h+a[i1][j1]+a[i2][j2]; if(i1==i2) dp[i1][j1][i2][j2]-=a[i1][j1]; } printf("%d",dp[m][n][m][n]); return 0; }