dpdpdp

Archie

很显然，每一层之间有最优子结构

那么，怎么转移呢，既然两个方向，那就加一维从哪里走

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define int long long
using namespace std;
int n,m;
int ma[1005][1005];
int f[2001][2001][3];
signed main(){
    scanf("%lld%lld",&n,&m);
//  cout<<n<<m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%lld",&ma[i][j]);
            //f[i][j][0]=f[i][j][1]=-9999999999;
        }
    }
    memset(f,0xc0,sizeof(f));
    f[1][1][0]=f[1][1][1]=ma[1][1];
    for(int j=1;j<=m;++j){
        for(int i=1;i<=n;++i){
            if(j!=1){
                f[i][j][0]=max(f[i][j][0],max(f[i][j-1][0],f[i][j-1][1])+ma[i][j]);
                f[i][j][1]=max(f[i][j][1],max(f[i][j-1][0],f[i][j-1][1])+ma[i][j]);
            }
            if(i!=1){
                f[i][j][0]=max(f[i][j][0],f[i-1][j][0]+ma[i][j]);
            }
        }
        for(int i=n;i>=1;--i){
            if(i!=n){
                f[i][j][1]=max(f[i][j][1],f[i+1][j][1]+ma[i][j]);
            }
        }
    }
    cout<<max(f[n][m][0],f[n][m][1]);
    return 0;
}