每日算法打卡：地宫取宝 day 16

本文主要是介绍每日算法打卡：地宫取宝 day 16，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接

1212. 地宫取宝

题目难度：中等

题目来源：第五届蓝桥杯省赛C++ A/B/C组,第五届蓝桥杯省赛Java B/C组

题目描述

X 国王有一个地宫宝库，是 $n\times m$ 个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是 $k$ 件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 $k$ 件宝贝。

输入格式

第一行 3 个整数，$n,m,k$，含义见题目描述。

接下来 $n$ 行，每行有 m 个整数 $C_i$ 用来描述宝库矩阵每个格子的宝贝价值。

输出格式

输出一个整数，表示正好取 $k$ 个宝贝的行动方案数。

该数字可能很大，输出它对 $1000000007$ 取模的结果。

数据范围

$1\le n,m\le 50$,
$1\le k\le 12$,
$0\le C_i\le 12$

输入样例1：

2 2 2
1 2
2 1 

输出样例1：

2 

输入样例2：

2 3 2
1 2 3
2 1 5 

输出样例2：

14 

题目分析

这道题和之前的摘花生的题目是十分类似，其实就是一个扩展与限制，这里有一个限制就是需要以严格递增的顺序拿，另一个限制就是最后拿到的数量必须是k件

我们仍然是采用集合的DP思想，对于集合$f(i,j,k,c)$这里的i，j表示当前的坐标，k表示当前取到了多少个，c表示取到物品的数值，确保其是递增的。他的意思就是，从七点走到i，j取了k件物品，最后一个物品的价值是c的所有合法方案的集合

对于这个集合如何进行状态计算，就是如何进行状态划分，因为这个题目的状态非常多，就需要逐步分析，就像剥洋葱一样，一层一层细分，第一层是按照位置分，分别从上向下走和从左向右走两种，第二层是按照第i，j个物品是否取得划分，那么对于取的情况下，对于每一个上一个物品的数值是多少再次进行划分

我们逐步分析每一种情况的状态计算具体是什么

对于从上往下的不取的情况$f(i,j,k,c)=f(i-1,j,k,c)$因为不取，所以对k和c没有任何影响，对于从左往右的情况也是相同的

对于取的情况来说，他需要满足在取的时候这个位置上的权值必定为c，因为在取之后c一定是之前所有取到的数值的最大值

这个问题我们需要考虑一下边界的初始化问题，起点有两种情况，第一种就是选择第一个位置的数字$f(1,1,1,w(1,1)=1$，如果不选择第一个位置的数字就是$f(1,1,0,-1)=1$当然这里的-1是不合法的，我们可以给所有的权值加1即可

示例代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 55,MOD=1000000007;int n,m,k;
int w[N][N];
int f[N][N][13][14];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][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; // 表示1，1位置已经初始化过了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&&v==w[i][j]) // 如果选择{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;}}}}}}int ans = 0;for(int i=0;i<=13;i++) ans = (ans + f[n][m][k][i])%MOD;cout<<ans<<'\n';return 0;
}

这篇关于每日算法打卡：地宫取宝 day 16的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---