lanqiao OJ 803 方格取数

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std ;
const int N = 1e3 +10 ,INF = 1e9 ;
int f[N][N][3] ;
int g[N][N] ;
int n , m ;
int main(){
    cin >> n >> m ;
    for(int i = 1 ; i <= n ;i ++){
        for(int j = 1 ; j <= m ; j ++){
            cin >> g[i][j] ;
        }
    }
    for(int j = 1 ; j <= m ; j ++){
        
        for(int i = 1 ; i <= n ; i ++){
            f[i][j][0] = max(f[i][j-1][0], max(f[i][j-1][1],f[i][j-1][2])) + g[i][j] ;
            f[i][j][1] = max(f[i-1][j][0] , f[i-1][j][1]) + g[i][j] ;
            if(j==1) f[i][j][0] = f[i][j][1];
            if(i==1) f[i][j][1] =  f[i][j][0] ;
            
            
        }
        
        for(int i = n ; i >= 1  ; i --){
            if(i==n) f[i][j][2]= f[i][j][0];
            else f[i][j][2] = max(f[i+1][j][0],f[i+1][j][2]) + g[i][j] ;
        
            if(j==1)
                f[i][j][2] = -INF;
            
        }
    }
    cout << max(f[n][m][0],max(f[n][m][1],f[n][m][2])) << endl ;
    return 0 ;
}