AcWing_1212 地宫取宝(DP)

10 Mar 2024 1874字 7分

AcWing

1212. 地宫取宝

动态规划。定义四维状态数组f[N][M][K][W]表示小明走到(n, m)的位置，恰好恰好取了k个宝贝时，最大价值为w的所有方案的总数量。

可以将f[n][m][k][w]分为以下若干个集合(n, m从1开始编号，为了将0作为特殊边界)：

  • 由(n - 1, m)的位置转移过来
    • 取了该位置((n, m)位置)的宝贝(此时要求w == c[i][j]，因为如果w > c[i][j]，一定不能取该宝贝；如果w < c[i][j]，也一定没有取该宝贝)
      • 由c == 0转移到c == m
      • 由c == 1转移到c == m
      • ……
      • 由c == m - 1转移到c == m
    • 没有取该位置((n, m)位置)的宝贝
  • 由(n, m - 1)的位置转移过来
    • 取了该位置((n, m)位置)的宝贝(此时要求w == c[i][j]，因为如果w > c[i][j]，一定不能取该宝贝；如果w < c[i][j]，也一定没有取该宝贝)
      • 由c == 0转移到c == m
      • 由c == 1转移到c == m
      • ……
      • 由c == m - 1转移到c == m
    • 没有取该位置((n, m)位置)的宝贝

保证将f[n][m][k][w]分为这些集合之后不重不漏。则对于普遍的f[n][m][k][w]，其值为这些方案数量的总数，有:

  1. f[n][m][k][w] = f[n - 1][m][k][w] + f[n][m - 1][k][w](两种前置转移，当不取当前位置的宝贝的情况，方案数)

  2. w == c[i][j]时，还有：

    f[n][m][k][w] += f[n - 1][m][k - 1][0] + f[n - 1][m][k - 1][1] + ... + f[n - 1][m][k - 1][w - 1]

    f[n][m][k][w] += f[n][m - 1][k - 1][0] + f[n][m - 1][k - 1][1] + ... + f[n][m - 1][k - 1][w - 1]

此外，为了区分初始状态的值和价值0，考虑将所有价值都+1，将初始价值定义为0.

那么，考虑边界条件，f[1][1][0][0] = 1, f[1][1][1][c[1][1]] = 1，即当在(1, 1)位置，不取任何宝贝，价值为初始状态，此为一种方案；当在(1, 1)位置，取该位置的宝贝，价值为该位置宝贝的价值，此为一种方案。

在执行状态转移时，顺手取个模，以满足题目要求。

算法的时间复杂度为$O(N * M * K * W * W)\approx 50\times 50 \times 12\times 12\times 12\approx 4320000$，可以过。

ps: 代码中使用w[N][M]表示上面说的c[N][M]，f[n][m][k][w]中该维度(第四维)的迭代使用b.

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
const int N = 55, M = 55, K = 15, W = 15;
const int MOD = 1000000007;
int f[N][M][K][W], w[N][M];
int main(){
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> w[i][j], w[i][j]++;
    f[1][1][0][0] = 1;
    f[1][1][1][w[1][1]] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i == 1 && j == 1) continue;
            for(int a = 0; a <= k; a++){
                for(int b = 0; b <= 12 + 1; b++){
                    f[i][j][a][b] = (f[i][j][a][b] + f[i - 1][j][a][b]) % MOD;
                    f[i][j][a][b] = (f[i][j][a][b] + f[i][j - 1][a][b]) % MOD;
                    if(a >= 1 && b == w[i][j]){
                        int sumCnt = 0;
                        for(int u = 0; u <= b - 1; u++){
                            sumCnt = (sumCnt + f[i - 1][j][a - 1][u]) % MOD;
                            sumCnt = (sumCnt + f[i][j - 1][a - 1][u]) % MOD;
                        }
                        f[i][j][a][b] = (f[i][j][a][b] + sumCnt) % MOD;
                    }
                }
            }
        }
    }
    int res = 0;
    for(int i = 0; i <= 12 + 1; i++) res = (res + f[n][m][k][i]) % MOD;
    cout << res << endl;
    return 0;
}