AcWing 1212. 地宫取宝

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1212. 地宫取宝原题链接中等

作者：

Daniel丶y , 2019-12-18 13:42:04 , 所有人可见 , 阅读 15631

215

95

题目链接： AcWing 1212 地宫取宝

题意：

先导条件：给定一个数$n\times m$地图，每个格子都放有不同价值的物品，从左上角出发到右下角，每一步往右或者往下走一步，面对每一个物品，可以拿走，也可以不拿，而且只有当前格子的物品大于所有已拿的物品价值，才能够拿这个物品
问题：问到达终点时，恰好拿够$k$个物品的方案数

解题思路：

这道题可以用四维DP解决，由于接触DP没多久，对于我来说确实是一个挑战，但是经过大半天的挣扎，算是把这道题的思路整理出来了，这里我模仿yxc的DP分析思路：用集合的思想考虑DP
第一个要想清楚的就是，要取得当前格子的物品，这个物品必须比当前所拥有的物品都大，所以有一个性质：后面拿的物品比前面的物品大
然后画出以下的分析图：

地宫取宝.png

难点在于状态计算部分，联想到01背包问题，对于每个物品，都有取或不取两种选择，而不取是肯定可以的，要取的话，要满足背包能放下这个条件
这里也一样，对于每个物品，都可以不选，也就是直接从上一步转移状态过来，但是如果要取得$(i,j)$位置的物品，就必须满足当前的$k$和$a[i][j]$相等，因为上面分析过了，如果现在取了$a[i][j]$，那么它肯定是现在所有物品最大的，这和我们一开始四维数组的定义是对应的
在具体的状态转移中，如果不选，就直接从上一步完完整整地把状态$cnt$和$k$转移过来；如果选，那上一步就应该选了$cnt-1$个物品，而且上一步身上所有物品最大值只能是$1\dots k-1$，把这些状态的方案数累加，就可以成为选择当前物品的条件

注意事项：

因为这道题的所有物品价值范围是$0\dots 12$，可以把他们全部都递增，范围就变成了$1\dots 13$，因为我们记录的是方案数，只关心各个物品之间的大小关系，具体数值不影响答案，但是这样的做法可以把$0$作为一个特殊边界来处理
整个过程不理解的话，可以用纸笔模拟一下，看看每个状态的数值应该是多少

代码如下：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 55;
const int M = 15;
const int MOD = 1e9 + 7;

int n, m, c;
int a[N][N];
// f[i][j][cnt][k] 表示：在 (i, j) 这个点，拿了 cnt 个物品，这些物品中价值最大的是 k
int f[N][N][M][M];

int main() {
  scanf("%d%d%d", &n, &m, &c);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      scanf("%d", &a[i][j]);
      a[i][j]++;
    }
  }
  // 两个边界初始化
  // 在起点 (1, 1) 处
  // 如果拿也只能拿 a[i][j] 这个物品，只有一种方案
  // 如果不拿，那就是 0 个物品，也是一个方案数
  // 由于物品价值已经增加了一个偏移量，现在价值的范围是 [1, 13]
  // 所以价值为 0 并不代表物品的价值，而是一个边界点
  f[1][1][0][0] = 1;
  f[1][1][1][a[1][1]] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      for (int cnt = 0; cnt <= c; cnt++) {
        for (int k = 0; k < M; k++) {
          // 不拿物品
          f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i - 1][j][cnt][k]) % MOD;
          f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i][j - 1][cnt][k]) % MOD;
          // 可以拿
          if (cnt > 0 && k == a[i][j]) {
            for (int s = 0; s < a[i][j]; s++) {
              f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i - 1][j][cnt - 1][s]) % MOD;
              f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i][j - 1][cnt - 1][s]) % MOD;
            }
          }
        }
      }
    }
  }
  // 最后把在终点 (n, m) 处拿 c 个物品的方案数累加
  int res = 0;
  for (int i = 1; i < M; i++) {
    res = (res + f[n][m][c][i]) % MOD;
  }
  printf("%d\n", res);
  return 0;
}

UPD:2020.10.5
以上代码的思路是枚举当前状态，然后枚举可能转移到当前状态的状态，然后从这些可能的状态中转移到当前状态，这样做有两个坏处，一是会多一层循环，时间复杂度增加，二是在一些题目中可能难以枚举以前对状态
因此这里再给出一种枚举当前状态，由当前状态转移到可能从当前状态达到的状态的代码。两种思路都是正确的，但必须两种都能熟练掌握

#include <bits/stdc++.h>

using namespace std;

const int N = 55, M = 15, mod = 1e9 + 7;

int n, m, c;
int a[N][N];
int f[N][N][M][M];

int main() {
  cin >> n >> m >> c;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> a[i][j];
      a[i][j]++;
    }
  }
  // 初始化
  f[1][1][0][0] = f[1][1][1][a[1][1]] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      for (int cnt = 0; cnt <= c; cnt++) {
        for (int k = 0; k < M; k++) {
          if (f[i][j][cnt][k]) {
            // 不取 (i+1,j) 的物品，可以直接从 (i,j) 转移到 (i+1,j)
            f[i + 1][j][cnt][k] = (f[i + 1][j][cnt][k] + f[i][j][cnt][k]) % mod;
            // 不取 (i,j+1) 的物品，可以直接从 (i,j) 转移到 (i,j+1)
            f[i][j + 1][cnt][k] = (f[i][j + 1][cnt][k] + f[i][j][cnt][k]) % mod;
            // 还可以取物品
            if (cnt + 1 <= c) {
              // 取 (i+1,j) 的物品，从 (i,j) 转移到 (i+1,j)
              if (a[i + 1][j] > k) {
                f[i + 1][j][cnt + 1][a[i + 1][j]] = (f[i + 1][j][cnt + 1][a[i + 1][j]] + f[i][j][cnt][k]) % mod;
              }
              // 取 (i,j+1) 的物品，从 (i,j) 转移到 (i,j+1)
              if (a[i][j + 1] > k) {
                f[i][j + 1][cnt + 1][a[i][j + 1]] = (f[i][j + 1][cnt + 1][a[i][j + 1]] + f[i][j][cnt][k]) % mod;
              }
            }
          }
        }
      }
    }
  }
  int res = 0;
  for (int i = 1; i < M; i++) {
    res = (res + f[n][m][c][i]) % mod;
  }
  cout << res << '\n';
  return 0;
}

说实话我觉得这题里物品的价值可能是 $0$ 这个设定挺坑人的……

184 评论

Noki1314 2022-10-20 15:33

555555我终于理解了，自己写的时候在a[i][j]++卡了好长时间，简而言之就是要是不把拿了价值为0和没拿物品的情况分开的话，拿了价值为0 的情况由于if (cnt > 0 && k == a[i][j])这个判断条件，会缺少一部分数值

18735996583 2023-03-16 15:44

看了你的评论我好像理解了
if (cnt > 0 && k == a[i][j]) {
for (int s = 0; s < a[i][j]; s++) {
f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i - 1][j][cnt - 1][s]) % MOD;
f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i][j - 1][cnt - 1][s]) % MOD;
}
这段代码如果价值存在0的话，那么要拿价值为0的物品，数组下标(int s = 0）必须变成(int s = -1）才能拿，但是这样数组下标会变成-1越界，所以必须让所有物品价值不低于1，

zxcpyy 2023-03-18 17:32 回复了 18735996583 的评论

价值为0的物品只会在第一个位置拿，以后不可能会拿，而第一个位置已经手动设置了值，不懂

18735996583 2023-03-21 09:59 回复了 zxcpyy 的评论

价值为0的物品不只会在第一个位置拿如果终点物品的价值为0，你只拿1个物品，偏偏就只把那个价值为0的终点的一个物品拿走了，这个时候如果没有a[i][j]++，就无法拿这个物品

18735996583 2023-03-21 10:05 回复了 zxcpyy 的评论

并且第1个位置手动设值，这个值其实是。用来统计。到i，j位置，一个物品也不拿一共有多少种走法

zxcpyy 2023-03-21 10:55 回复了 18735996583 的评论

懂了谢谢啦hh

黑月 2023-02-27 18:57

我想问问为啥要这么写if (cnt > 0 && k == a[i][j]) {
for (int s = 0; s < a[i][j]; s++) {
这边没看明白，求大佬讲一下

诠释 2023-03-04 23:30

因为当前这一步求的是f[i][j][cnt][k]中取了[i,j]位置宝物之后的状态，你要保证a[i][j]==k，才能得到f[i][j][cnt][k]（弄懂f这个四维数组的定义）。循环是表示，任何一个方案中，只要s<a[i][j]，他就可以通过加上一个宝物后得到f[i][j][cnt][k]（k是最大值），所以要遍历从0~a[i][j]的所有情况。

jyjymm 7个月前

常见问题: 为什么取第(i,j)物品的时候要满足 c == w[i][j] ？以及为什么状态转移方程2 用的是0…c累加
这个博客解释的有 >>点击<<

Mxeron 2022-03-06 09:50

自加的原因应该是：dp[1][1][0][0]本身是有值的，并不是=0，无法避免cnt必须从0开始遍历，所以只能是自加，才能把最开始第一个位置的状态纳入考虑，后续位置为0时，自加也成立。

Daniel丶y 2022-03-07 13:34

是的。

zhensi666 2023-03-30 19:35

nb,佬

xiojoy 11个月前

可以三维dp，且时间复杂度与价值大小无关。
https://www.acwing.com/activity/content/code/content/7666825/

sixwalter 2022-12-05 20:40

这题目坑好多

熊猫BearCat 12天前

所以不能拿和能拿但是不拿是转移方程是一样的是吧，大佬

Daniel丶y 5天前

对。你可以这么理解，在一个位置上，只有两种选择：拿或者不拿。不能拿和能拿但是不拿本质上都是不拿。

QCMT 2023-10-24 09:15

我有两个问题，// 不拿物品
f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i - 1][j][cnt][k]) % MOD;
f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i][j - 1][cnt][k]) % MOD;
这第一行代码的 (f[i][j][cnt][k] +这个f[i][j][cnt][k]不应该多余么，每次循环新的cnt和k,那么(f[i][j][cnt][k] +中的f[i][j][cnt][k] 都等于0不是多余的么，为什么删掉了就不对了
还有一个就是
f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i - 1][j][cnt - 1][s]) % MOD;
f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i][j - 1][cnt - 1][s]) % MOD;
当k==a[i][j]时，拿物品的那段代码不就会把不拿的代码的存储的物品个数覆盖吗

Daniel丶y 2023-10-27 04:37

不知道我是否理解对了你的问题。
$f[i][j][cnt][k]$ 无论什么时候都是代表一个集合，所以无论在计算“不拿物品”还是“拿物品”的时候，都从可能的地方找到能转变成这个集合的其它集合。
就好像你拿着一个袋子四处装东西，在 A 地发现了物品放入了袋子，袋子里的物品肯定是累加呀，即使你的袋子当前是空的，但是累加也不会导致答案错误。
至于说例子的话，虽然大部份的 $f[i][j][cnt][k]$ 都是 $0$ ，但是初始状态是已经手动赋值了的，如果删掉的话应该是没有计算到初始的状态。
第二个问题还是如同上面所说，这里是累加，只是新增了拿物品的情况，并没有覆盖。

QCMT 2023-11-26 10:43 回复了 Daniel丶y 的评论

感谢佬

becklee 2023-02-28 11:45

有一个疑惑，f[i][j][u][v]到底是存的真实方案数还是% mod后的方案数
- 如果是真实方案数，为什么还5层for循环里还需要% mod
- 如果是% mod后的方案数，那么为什么还需要res = (res + f[n][m][c][i] ) % mod

Daniel丶y 2023-03-01 13:48

是取模后的方案数，最后要求的结果也是取模后的方案数，所以一直取模就行。

关静小朋友 2023-02-26 19:37

大佬请问下，为什么这样写不对呢？感觉也可以把选上当前数的所有情况都覆盖呀

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(i==1 && j==1 ) continue;
            for(int l=0;l<=k;l++)
            {
                for(int m=0;m<=13;m++)
                {
                    int &v = dp[i][j][l][m];
                    v=(v+dp[i-1][j][l][m])%MOD ;
                    v=(v+dp[i][j-1][l][m])%MOD ;
                    if(l>0 &&   m<arr[i][j])
                    {
                        v= (v+ dp[i-1][j][l-1][m]   )%MOD ;
                        v= (v + dp[i][j-1][l-1][m]   )%MOD ;
                    }
                }
            } 
        }
    }