题解：P7074 [CSP-J2020] 方格取数

一道好 dp 题。

方法一：

我们可以用记忆化搜索来解决。

数组状态

dp_{i,j,0/1}

表示从上方或者下方走到坐标

{i,j}

的点的最大答案。

然后就是判断当前 dfs 到的点有没有被记过答案，如果记过就继续往下搜，如果没搜过就更新一下答案。

代码就不给了，因为没这么写。

方法二：

题解这里提供一个滚动数组方法，我们的 dp 数组这开到

dp_{i,j}

，把后面的一个 bool 变量用两个新数组

up_{i,j}

和

down_{i,j}

作为代替。

转移方程：

up_{i,j}=\max(up_{i+1,j},dp_{i-1,j})+a_{i,j}

。

down_{i,j}=\max(down_{i-1,j},dp_{i,j-1})+a_{i,j}

。

dp_{i,j}=\max(up_{i,j},down_{i,j})

。

其实就是看看是向上走答案大还是向下走答案大然后直接更新就行了。

代码：

CPP

#include<iostream>
#include<cstring>
#define int long long
#define PII pair<int,int>

using namespace std;
const int N=1005;
int a[N][N],dp[N][N];
int up[N][N],down[N][N];
int n,m;
signed main() {
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j) cin>>a[i][j];
	memset(down,128,sizeof(down));
	memset(up,128,sizeof(up));
	memset(dp,128,sizeof(dp));
	dp[1][1]=a[1][1];
	for(int i=2;i<=n;++i) {
		dp[i][1]=dp[i-1][1]+a[i][1];
	}
	for(int j=2;j<=m;++j) {
		for(int i=1;i<=n;++i){
			down[i][j]=max(down[i-1][j],dp[i][j-1])+a[i][j];
		}
		for(int i=n;i>=1;--i){
			up[i][j]=max(up[i+1][j],dp[i][j-1])+a[i][j];
		}
		for(int i=1;i<=n;++i){
			dp[i][j]=max(up[i][j],down[i][j]);
		}
	}
	cout<<dp[n][m];
	return 0;
}

题解：P7074 [CSP-J2020] 方格取数

文章操作

方法一：

方法二：

相关推荐

评论

题解：P7074 [CSP-J2020] 方格取数