P7074 [CSP-J2020] 方格取数

Problem

相关算法：\(DP\)。

题意简述

给你一个方格图，每次只能向上、向右、向下走。

现在求：经过所有点取到的数字和的最大值。

思路

动态规划。

对于每一列而言，如果某个点向上走了，就不可能再向下走。向下走了同理。

所以我们可以把两种情况都尝试一遍，每个点而言，如果是处于向下的状态，那么

\(ma = -10^{18},ma = max(ma,f_{i,j-1}) + a_{i,j}\);

\(f_{i,j} = max(ma, f_{i_j});\)

如果处在向上的状态，同理。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;
int a[N][N];
typedef long long ll;
ll f[N][N], n, m;
int main() {
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	memset(f, -0x7f, sizeof(f));
	ll ma;
	f[1][0] = 0;
	for (int j = 1; j <= m; j++) {
		ma = -1e18;
		for (int i = 1; i <= n; i++) {
			ma = max(ma, f[i][j - 1]) + a[i][j];
			f[i][j] = max(f[i][j], ma);
		}
		ma = -1e18;
		for (int i = n; i >= 1; i--) {
			ma = max(ma, f[i][j - 1]) + a[i][j];
			f[i][j] = max(f[i][j], ma);
		}
		
	}
	printf("%lld", f[n][m]);
	return 0;
}