DP 95分 但开了long long
查看原帖
DP 95分 但开了long long
494992
underline__jian楼主2022/5/12 18:45
#include<iostream>
#include<algorithm>
#define re register
#define N 1e5+15
#define M 1048
using namespace std;
unsigned long long a[M][M],f[1002][1002][3],n=-1e7,m;
int main(){
    cin>>n>>m;
    for(re int i=1;i<=n;i++)
        for(re int j=1;j<=m;j++){
            cin>>a[i][j];
            f[i][j][0]=-1000000;
            f[i][j][1]=-1000000;
            f[i][j][2]=-1000000;
        }
    for(int i=1;i<=n;i++) f[i][1][1]=f[i-1][1][1]+a[i][1];
    for(int j=2;j<=m;j++){
        for(int i=1;i<=n;i++){
            f[i][j][0]=max(max(f[i][j-1][0],f[i][j-1][1]),f[i][j-1][2])+a[i][j];
            if(i>=2) f[i][j][1]=max(f[i-1][j][0],f[i-1][j][1])+a[i][j];
        }
        for(int i=n-1;i>=1;i--) f[i][j][2]=max(f[i+1][j][0],f[i+1][j][2])+a[i][j];
    }
    cout<<max(max(f[n][m][0],f[n][m][1]),f[n][m][2]); 
    return 0;
}
2022/5/12 18:45
加载中...