题解：P8612 [蓝桥杯 2014 省 AB] 地宫取宝

一道简单的

\texttt{dfs}

搜索题。

对于当前的点，我们分类讨论以下

4

种情况：

向下走，不拿；
向右走，不拿；
向下走，拿；
向右走，拿。

注意，我们还需要特判两种情况：

未到终点但是已经拿满了（即拿了 $k$ 个物品）；
到了终点但是没有拿满，但是拿走的物品价值最大。

由于直接搜索的理论复杂度为

4^{50}

次方，所以我们需要考虑使用记忆化搜索。

记忆化搜索，简单来说，就是对于每个已经搜索过的或者搜到了的点，我们将答案存到一个数组中保存，当再次搜索到时，直接返回。

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, k, mp[55][55], vis[55][55][15][15];
int dfs(int x, int y, int maxn, int cnt) {
	if (x == n + 1 || y == m + 1) return 0; // 如果到达终点了
	if (vis[x][y][maxn + 1][cnt] != -1) return vis[x][y][maxn + 1][cnt];
	// 如果记忆数组中已经有值了，直接返回
	int tmp = 0; // 用于记录答案
	if (x == n && y == m) {
		if (cnt == k || (cnt == k - 1 && mp[x][y] > maxn)) tmp ++;
		// 分类讨论的两种情况
	} else {
		tmp += dfs(x, y + 1, maxn, cnt); // 不拿走
		if (mp[x][y] > maxn) tmp += dfs(x, y + 1, mp[x][y], cnt + 1);
		// 如果没有超过最大值，拿走
		tmp += dfs(x + 1, y, maxn, cnt); // 不拿走
		if (mp[x][y] > maxn) tmp += dfs(x + 1, y, mp[x][y], cnt + 1);
		// 如果没有超过最大值，拿走
	}
	return vis[x][y][maxn + 1][cnt] = tmp % 1000000007;
	// 将值赋给记忆数组，然后返回
}
signed main() {
	ios :: sync_with_stdio(false);
	cin . tie(nullptr);
	memset(vis, -1, sizeof(vis)); // 初始时记忆数组全部赋为-1
	cin >> n >> m >> k;
	for ( int i = 1; i <= n; i ++)
		for ( int j = 1; j <= m; j ++) cin >> mp[i][j];
	cout << dfs(1, 1, -1, 0) << endl;
	return 0;
}

题解：P8612 [蓝桥杯 2014 省 AB] 地宫取宝

文章操作

相关推荐

评论

题解：P8612 [蓝桥杯 2014 省 AB] 地宫取宝