AcWing 1212. 地宫取宝 题解

题目

思路

闫氏DP分析法：

状态表示

$f[i][j][k][c]$

集合

所有从起点走到$(i,j)$，且已经取了$k$件物品，且最后一件物品的价值为$c$的方案数

因为“走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）”
所以每一步，如果取，那它就必然是之前取过的所有数的最大值

属性

方案总数

状态计算

$f[i][j][k][c]$的来源有四种：

• 1：最后一步是从上往下走，且不取当前位置的宝物
  $f[i-1][j][k][c]$
• 2：最后一步是从左往右走，且不取当前位置的宝物
  $f[i][j-1][k][c]$

第三种和第四种来源出现的必要条件：
当前k得大于0，因为当前是”取了的“，不可能为0否则就矛盾了
当前位置的宝物价值得等于c，因为取了的这个物品就是最后一件物品了

• 3：最后一步是从上往下走，且取当前位置的宝物
  遍历所有上一步的可能的价值c，加到答案上就行

• 4：最后一步是从左往右走，且取当前位置的宝物
  遍历所有上一步的可能的价值c，加到答案上就行

边界处理

$f[1][1][1][w[1][1]]=1;$在起点处，如果取得话，最大物品的价值为起点处的宝物价值，这样的方案就只有一个
$f[1][1][0][-1]=1;$在起点处，如果不取的话，取了0件，最大价值为-1，取-1是为了方便后面自然转移，但是我们又发现，数组下标没法有-1，怎么办，我们可以在读入地宫的时候，把所有宝物的价值+1，这样用0替代-1

代码

#include<iostream>
using namespace std;
const int N=55,MOD=1e9+7;
int f[N][N][15][14];
int w[N][N];
int n,m,k;
int main()
{scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++)   for(int j=1;j<=m;j++){scanf("%d",&w[i][j]);w[i][j]++;  //读入时，人为的全部+1，为了后面拿0替代-1}f[1][1][1][w[1][1]]=1;   //初始化边界f[1][1][0][0]=1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)       //遍历整个地宫的所有点{if(i==1&&j==1) continue;   //因为初始化的时候做过了，不需要再考虑for(int u=0;u<=k;u++)       //遍历所有可能的方案数for(int v=0;v<=13;v++)     //遍历所有可能的最后取的（最大的）价值{int &val=f[i][j][u][v];val=(val+f[i-1][j][u][v])%MOD;val=(val+f[i][j-1][u][v])%MOD;if(u>0&&w[i][j]==v)    //如果当前考虑的方案数是比0大的，且当前价值就是当前位置的宝物价值，说明取了当前位置的宝物{for(int c=0;c<v;c++)  //遍历上一步所有可能的宝物价值取值{val=(val+f[i-1][j][u-1][c])%MOD;val=(val+f[i][j-1][u-1][c])%MOD;}}}}long long res=0;for(int i=0;i<=13;i++) res=(res+f[n][m][k][i])%MOD;  //算上所有终点的方案数为k的方案总数printf("%lld",res);                                  //主要是最后取得价值不同return 0;
}