AcWing 2770. 方格取数
原题链接
中等
作者:
陈宜轩
,
2024-12-21 14:00:11
,
所有人可见
,
阅读 3
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[1005][1005];
int s[1005][1005];
int x[1005][1005];
int n,m,a[1005][1005];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++)dp[i][1]=a[i][1]+dp[i-1][1];
for(int i=2;i<=m;i++){
//cout<<dp[1][i]<<' ';
for(int j=1;j<=n;j++)
s[j][i]=dp[j][i-1]+a[j][i],x[j][i]=dp[j][i-1]+a[j][i];
for(int j=n-1;j>=1;j--){
s[j][i]=max(s[j][i],s[j+1][i]+a[j][i]);
}
for(int j=2;j<=n;j++){
x[j][i]=max(x[j][i],x[j-1][i]+a[j][i]);
}
for(int j=n;j>=1;j--){
dp[j][i]=max(s[j][i],x[j][i]);
}
}
/*for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)cout<<dp[i][j]<<'\t';
cout<<"\n";
}*/
cout<<dp[n][m];
//<<s[i][j]<<'\t'<<x[i][j]<<'\t'
return 0;
}