从P1004改的,WA on #6,#8,#9
code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=51;
int dp[N+N][N][N],s[N][N];
signed main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>s[i][j];
}
}
for(int k=1;k<=n+m;k++){
for(int i=1;i<=min(k,n);i++){
for(int j=1;j<=min(k,m);j++){
dp[k][i][j]=max({dp[k-1][i][j-1],dp[k-1][i][j],dp[k-1][i-1][j-1],dp[k-1][i-1][j]})+s[k-i+1][i]+s[k-j+1][j];
if(i==j) dp[k][i][j]-=s[k-i+1][i];
}
}
}
cout<<dp[n+m][n][m];
return 0;
}