P7074
状态
\[up[i][j]表示这一步向上或向右走到(i,j)的最大价值 \]\[down[i][j]表示这一步向下或向右走到(i,j)的最大价值 \]\[dp[i][j]表示走到(i,j)的最大价值 \]- 第一维表示行,第二维表示列
转移
-
第一列和最后一列只能从上往下走(最后一列还可以从左往右)
-
第一列
- 第2~m-1列
- 最后一列
- 因为每一列都是单独处理,所以列这一维没有啥用,去掉即可
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int up[1001],down[1001],dp[1001];
int in[1001][1001];
signed main(){
// freopen("1.in","r",stdin);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
cin>>in[i][j];
}
dp[1]=in[1][1];
for(int i=2;i<=n;i++)
dp[i]=dp[i-1]+in[i][1];
for(int i=2;i<m;i++){
memset(up,0,sizeof(up));
memset(down,0,sizeof(down));
up[n]=dp[n]+in[n][i];
down[1]=dp[1]+in[1][i];
for(int j=n-1;j>=1;j--)
up[j]=max(dp[j],up[j+1])+in[j][i];
for(int j=2;j<=n;j++)
down[j]=max(dp[j],down[j-1])+in[j][i];
for(int i=1;i<=n;i++) dp[i]=max(up[i],down[i]);
}
dp[1]=dp[1]+in[1][m];
for(int i=2;i<=n;i++)
dp[i]=max(dp[i-1],dp[i])+in[i][m];
cout<<dp[n]<<"\n";
}
标签:int,max,up,down,1001,P7074,dp
From: https://www.cnblogs.com/wangyangjena/p/17452354.html