题解

#include<iostream>
using namespace std;
#define max(a,b,c) max(max(a,b),c)
typedef long long ll;
const int N=1005;
const ll minn=-1145141919810;
ll a[N][N],dp[N][N][2];
int n,m;
ll DP(ll x,ll y,ll z){
    if(x<1||x>n||y<1||y>m) return minn;
    if(dp[x][y][z]!=minn) return dp[x][y][z];
    if(z==0){
        dp[x][y][z]=max(DP(x+1,y,0),DP(x,y-1,0),DP(x,y-1,1))+a[x][y];
    }
    else{
        dp[x][y][z]=max(DP(x-1,y,1),DP(x,y-1,0),DP(x,y-1,1))+a[x][y];
    }
    return dp[x][y][z];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            dp[i][j][0]=dp[i][j][1]=minn;
        }
    }
    dp[1][1][1]=dp[1][1][0]=a[1][1];
    cout<<DP(n,m,1);
    return 0;
}