3维dp
#include<bits/stdc++.h>
using namespace std;
int n,m,a[55][55],dp[105][55][55];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cin>>a[i][j];
}
for(int l=2;l<=n+m;l++){
for(int i=1;i<=n&&i<l;i++){
for(int j=1;j<=n&&j<l;j++){
int x=l-i,y=l-j;
dp[l][j][i]=max(max(dp[l-1][j][i],dp[l-1][j-1][i]),
max(dp[l-1][j][i-1],dp[l-1][j-1][i-1]))+a[j][y];
if(!(i==j&&x==y)) dp[l][j][i]+=a[i][x];
}
}
}
cout<<dp[n+m][n][n];
return 0;
}
人生苦短,我用 EK
Orz