自动搬运

查看原文

来自洛谷，原作者为

	Dry_ice Я всегда буду любить мисс Tracy Reznik.

搬运于2025-08-24 22:26:24，当前版本为作者最后更新于2020-11-12 22:06:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

upd 2022.08.08：修正方向，感谢

uogu.com.cn/user/235121)、

Description

给定一个 $n\cdot m$ 矩阵，找一条从 $(1,1)$ 到 $(n,m)$ 权值和最大的路径，每次只准向上、下、右三个方向走。

$\text{Solution\ 1}$：暴力$\text{dfs}$

概述：这种算法比较简单，不需要动头脑，直接三方向深搜即可。

时间复杂度：$\mathcal{O}(3^{nm})$

期望得分：$20$ 分

$\text{Solution\ 2}$：最优性剪枝

概述：考场上我只想到了这种方法（太菜了。我们设 $F_{i,j,0}$ 表示从一个格子上方走到该格子的路径最大和，$F_{i,j,1}$ 表示从一个格子右方走到该格子的路径最大和，$F_{i,j,2}$ 表示从一个格子下方走到该格子的路径最大和。如果搜到相同的状态则判断是否比原 $F$ 值更大，如果更优则更新答案，否则退出该状态。

时间复杂度：视具体数据而定，当格子权值差值较大时能拿到较多分数。

期望得分：$40$ 分

考场 $\text{code}$

#include <stdio.h>
const int dx[] = {1, 0, -1}, dy[] = {0, 1, 0};
typedef long long LL;
int n, m; bool vis[1005][1005];
LL w[1005][1005], f[1005][1005][3], ans = -20000000000;
inline LL mx(LL p, LL q) {return p > q ? p : q;}
inline void dfs(int x, int y, int from, LL now) {
	if (x == n && y == m) {
		ans = mx(now, ans);
		return;
	}
	if (f[x][y][from] > now) return;
	else f[x][y][from] = now;
	for (int i = 0, xx, yy; i < 3; ++i) {
		xx = x + dx[i]; yy = y + dy[i];
		if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && !vis[xx][yy]) {
			vis[xx][yy] = true;
			dfs(xx, yy, i, now + w[xx][yy]);
			vis[xx][yy] = false;
		}
	}
}
int main(void) {
//	freopen("number.in", "r", stdin); freopen("number.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			scanf("%lld", &w[i][j]);
			f[i][j][0] = f[i][j][1] = f[i][j][2] = -20000000000;
		}
	vis[1][1] = true;
	dfs(1, 1, 0, w[1][1]);
	printf("%lld\n", ans);
	return 0;
}

$\text{Solution\ 3}$：记忆化搜索

概述：这才是正解。我们设 $F_{i,j,0}$ 表示从一个格子下方走到该格子的路径最大和，$F_{i,j,1}$ 表示从一个格子上方走到该格子的路径最大和。如果搜到以前搜过的状态则直接返回搜过的最大和（也就是 $F$ 中的值），否则继续搜索到达该格时的最大和。

时间复杂度：$\mathcal{O}(nm)$

期望得分：$100$ 分

$\text{ac\ code}$

#include <stdio.h>
typedef long long LL;
const LL min_ll = -1e18;
int n, m; LL w[1005][1005], f[1005][1005][2];
inline LL mx(LL p, LL q, LL r) {return p > q ? (p > r ? p : r) : (q > r ? q : r);}
inline 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] = mx(dfs(x + 1, y, 0), dfs(x, y - 1, 0), dfs(x, y - 1, 1)) + w[x][y];
    else f[x][y][from] = mx(dfs(x - 1, y, 1), dfs(x, y - 1, 0), dfs(x, y - 1, 1)) + w[x][y];
    return f[x][y][from];
}
int main(void) {
//	freopen("number.in", "r", stdin); freopen("number.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			scanf("%lld", &w[i][j]);
			f[i][j][0] = f[i][j][1] = min_ll;
		}
    f[1][1][0] = f[1][1][1] = w[1][1];
	printf("%lld\n", dfs(n, m, 1));
	return 0;
}

The end. Thanks.

记得点赞（qwq