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

动态规划 dp

方格取数类似于数字三角形，均可以使用动态规划直接秒杀.

但此题有 $3$ 个方向：上、右、下.所以可以定义一个三维数组 dp 数组.

假设 $f_{i, j, 1}$ 是从右、上方到达 $(i,j)$ 的和的最大值.

又有 $f_{i, j, 0}$ 是从右、下方到达 $(i,j)$ 的和的最大值.

我们可以先确定目标：$f_{n,m,1}$.为什么不是 $f_{n,m,0}$ 呢？因为小熊不可能从 $(n,m)$ 的下方到达终点.

状态转移

$f_{i,j,0} = max(f_{i+1,j,0}, max(f_{i,j-1,0}, f_{i,j-1,1})) + a_{i,j}$.

$f_{i,j,1} = max(f_{i-1,j,1}, max(f_{i,j-1,0}, f_{i,j-1,1})) + a_{i,j}$.

$a_{i,j}$ 表示当前各自的值.

当方向为 $0$ 时，说明小熊要往下方走，或者是右边走，但往右边走不管方向是 $0$ 或 $1$

均可以走.所以三者要取 $max$ 值.最后加上当前各自的值.

方向为 $1$ 时同理.

初始化

给 $f$ 数组中的格子赋一个较小的初值，类似于 $-10^{18}$.

然后将小熊的起点，即坐标 $(1,1)$ 的初值赋值如下:

f[1][1][0] = f[1][1][1] = a[1][1]

注意点

要开 long long！！！.

代码

这里使用类似于记忆化搜索的方式.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long ll;
const ll min_ll = -1e18;
int n, m;
ll a[1005][1005], f[1005][1005][2];

ll dfs(int x, int y, int from) {
    // 出界了
	if (x < 1 || x > n || y < 1 || y > m) return min_ll;
    // 有值了，返回
	if (f[x][y][from] != min_ll) return f[x][y][from];
    // 状态转移
	if (from == 0) f[x][y][from] = max(dfs(x + 1, y, 0), max(dfs(x, y - 1, 0), dfs(x, y - 1, 1))) + a[x][y];
	else f[x][y][from] = max(dfs(x - 1, y, 1), max(dfs(x, y - 1, 0), dfs(x, y - 1, 1))) + a[x][y];
	return f[x][y][from]; // 希望得到的结果
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%lld", &a[i][j]);
			f[i][j][0] = f[i][j][1] = min_ll; // 赋初值
		}
	}
	f[1][1][0] = f[1][1][1] = a[1][1]; // 赋初值
	printf("%lld", dfs(n, m, 1)); // 目标
	return 0;
}