蒟蒻15分二维dp求调
查看原帖
蒟蒻15分二维dp求调
1013142
Chizuru_Ichinose楼主2023/8/26 10:15
#include<bits/stdc++.h>
using namespace std;
const int kMax=1e3+5;
int n,m,a[kMax][kMax],f[kMax][kMax],on[kMax][kMax],un[kMax][kMax];
bool vis[kMax][kMax];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    f[1][1]=a[1][1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            on[i][j]=max(on[i+1][j],f[i][j-1])+a[i][j];
            un[i][j]=max(un[i-1][j],f[i][j-1])+a[i][j];
            f[i][j]=max(on[i][j],un[i][j]);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}
2023/8/26 10:15
加载中...