标签：cnt return val int dfs 地宫 取宝 dp

一、题目描述

[蓝桥杯 2014 省 AB] 地宫取宝

二、问题简析

一开始，我采用 \(bfs\) 进行搜索，出现了超出内存限制的问题。所以，要进行记忆化搜索，重新采用 \(dfs\)。

2.1 暴力搜索

令 \(dfs(i, j, cnt, val) =\) 从 \((i, j)\) 开始，有几种路线拿到 \(k\) 件物品（此时已经取了 \(cnt\) 件，最大值为 \(val\)）。

\[dfs(i, j, cnt, val) = \begin{cases} dfs(i+1, j, cnt, val) + dfs(i, j+1, cnt, val) &,val \geq A[i][j] \\ dfs(i+1, j, cnt, val) + dfs(i, j+1, cnt, val)+dfs(i+1, j, cnt+1, A[i][j]) + dfs(i, j+1, cnt+1, A[i][j]) &,val < A[i][j] \end{cases} \]

有两种情况可以认为满足要求：

• 1、到达 \((n-1,m-1)\) 时，\(cnt==k\)，则 return 1。
• 2、到达 \((n-1,m-1)\)时，\(cnt==k-1\) 且 \(val < A[n-1][m-1]\)，则 return 1。
• 3、其余到达 \((n-1,m-1)\) 的情况，都 return 0。

2.2 记忆化数组

我们设置一个记忆化数组 dp[i][j][cnt][val] 存储搜索中的结果。有几点需要注意：

• 1、因为返回值可能为 0，所以记忆化数组要初始化为 -1。

memset(dp, -1, sizeof(dp));

• 2、我们第一次调用 \(dfs\) 时， val 的值要为 -1，显然不满足数组的要求。所以，在存储时，所有的 val 都 +1。

---

三、AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

typedef pair<int, int> P;

typedef struct
{
	P loc;
	int cnt, val;
} node;

int A[53][53], n, m, k, ans;
int dx[2] = {1, 0};
int dy[2] = {0, 1};
int dp[53][53][14][14];

bool check(P loc)
{
	if (0 <= loc.first && loc.first < n && 0 <= loc.second && loc.second < m)
		return true;
	return false;
}

ll dfs(int x, int y, int cnt, int val)
{
	if (dp[x][y][cnt][val + 1] >= 0)
		return dp[x][y][cnt][val + 1];
	
	if (x == n - 1 && y == m - 1)
	{
		if (cnt == k)
			return dp[x][y][cnt][val + 1] = 1;
		if (cnt == k - 1 && A[x][y] > val)
			return dp[x][y][cnt][val + 1] = 1;
			
		return dp[x][y][cnt][val + 1] = 0;
	}
	
	ll ret = 0;
	for (int i = 0; i < 2; i++)
	{
		P nt = P(x + dx[i], y + dy[i]);
		if (check(nt))
		{
			if (A[x][y] > val)
				ret = (ret + dfs(nt.first, nt.second, cnt + 1, A[x][y])) % MOD;
			ret = (ret + dfs(nt.first, nt.second, cnt, val)) % MOD;
		}
	}

	return dp[x][y][cnt][val + 1] = ret;
}

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> A[i][j];
	
	memset(dp, -1, sizeof(dp));
	cout << dfs(0, 0, 0, -1) << endl;
	
	return 0;	
}

---

完

标签：cnt,return,val,int,dfs,地宫,取宝,dp
From： https://www.cnblogs.com/hoyd/p/18049780