考虑朴素 DP。定义 \(f_{i,j,i2,j2}\) 表示两个人分别在 \((i,j),(i2,j2)\) 时获得的最大收益。复杂度 \(O(n^4)\)，不行。
我们换种方法，定义 \(f_{st,x,y}\) 表示两人同时走了 \(st\) 步，分别向右走了 \(x,y\) 步。显然如果向右的步数确定了，向下的也确定了。
转移方程如下：
\[f_{st,x,y}=\max(f_{st-1,x,y},f_{st-1,x-1,y},f_{st-1,x,y-1},f_{st-1,x-1,y-1})+a_{i,j}+a_{i2,j2}-(x==y)\cdot a_{i,j} \]复杂度 \(O(n^3)\)。注意边界。
code：
#include<bits/stdc++.h>
using namespace std;
const int N=50+5;
int n,m,f[N*2][N][N],a[N][N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>m>>n;
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
cin>>a[i][j];
}
}
memset(f,~0x3f,sizeof(f));
f[0][0][0]=a[1][1];
for(int st=1;st<=n+m-2;++st){
for(int x=max(st-m+1,0);x<=min(n-1,st);++x){
for(int y=max(st-m+1,0);y<=min(n-1,st);++y){
int i=st-x+1,j=x+1,i2=st-y+1,j2=y+1;
f[st][x][y]=f[st-1][x][y];
if(x)f[st][x][y]=max(f[st][x][y],f[st-1][x-1][y]);
if(y)f[st][x][y]=max(f[st][x][y],f[st-1][x][y-1]);
if(x&&y)f[st][x][y]=max(f[st][x][y],f[st-1][x-1][y-1]);
f[st][x][y]+=a[i][j]+a[i2][j2];
if(x==y)f[st][x][y]-=a[i][j];
}
}
}
cout<<f[n+m-2][n-1][n-1]<<endl;
return 0;
}