CC班题解

#include<bits/stdc++.h>
//#include <windows.h>
//#include <conio.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+5;
ll dp[maxn][maxn][2];
ll a[maxn][maxn];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cin>>a[i][j];
}
for(int i=0;i<=n+1;i++)
for(int j=0;j<=m+1;j++)dp[i][j][0]=dp[i][j][1]=-1e12;
dp[1][1][1]=a[1][1],dp[1][1][0]=a[1][1];
for(int i=2;i<=n;i++)dp[i][1][0]=dp[i-1][1][0]+a[i][1];
for(int j=2;j<=m;j++){
for(int i=1;i<=n;i++){
dp[i][j][0]=max(dp[i-1][j][0],max(dp[i][j-1][0],dp[i][j-1][1]))+a[i][j];
}
for(int i=n;i>=1;i--){
dp[i][j][1]=max(dp[i+1][j][1],max(dp[i][j-1][0],dp[i][j-1][1]))+a[i][j];
}
}
cout<<dp[n][m][0];
return 0;
}