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

U•ェ•*U · 2024-11-28 17:00:08 · 题解

一道简单的 \texttt{dfs} 搜索题。

对于当前的点，我们分类讨论以下 4 种情况：

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

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

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

由于直接搜索的理论复杂度为 4^{50} 次方，所以我们需要考虑使用记忆化搜索。

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

#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;
}