怎么自己创建小程序,广州做网站优化费用,临西县建设网站,单页网站怎么赚钱文章目录 原题链接题目描述输入格式输出格式数据范围输入样例1#xff1a;输出样例1#xff1a;输入样例2#xff1a;输出样例2#xff1a; 题目分析示例代码 原题链接
1212. 地宫取宝
题目难度#xff1a;中等
题目来源#xff1a;第五届蓝桥杯省赛C A/B/C组,第五届蓝… 文章目录 原题链接题目描述输入格式输出格式数据范围输入样例1输出样例1输入样例2输出样例2 题目分析示例代码 原题链接
1212. 地宫取宝
题目难度中等
题目来源第五届蓝桥杯省赛C A/B/C组,第五届蓝桥杯省赛Java B/C组
题目描述
X 国王有一个地宫宝库是 n × m n \times m n×m 个格子的矩阵每个格子放一件宝贝每个宝贝贴着价值标签。
地宫的入口在左上角出口在右下角。
小明被带到地宫的入口国王要求他只能向右或向下行走。
走过某个格子时如果那个格子中的宝贝价值比小明手中任意宝贝价值都大小明就可以拿起它当然也可以不拿。
当小明走到出口时如果他手中的宝贝恰好是 k k k 件则这些宝贝就可以送给小明。
请你帮小明算一算在给定的局面下他有多少种不同的行动方案能获得这 k k k 件宝贝。
输入格式
第一行 3 个整数 n , m , k n,m,k n,m,k含义见题目描述。
接下来 n n n 行每行有 m 个整数 C i C_i Ci 用来描述宝库矩阵每个格子的宝贝价值。
输出格式
输出一个整数表示正好取 k k k 个宝贝的行动方案数。
该数字可能很大输出它对 1000000007 1000000007 1000000007 取模的结果。
数据范围 1 ≤ n , m ≤ 50 1 \le n,m \le 50 1≤n,m≤50, 1 ≤ k ≤ 12 1 \le k \le 12 1≤k≤12, 0 ≤ C i ≤ 12 0 \le C_i \le 12 0≤Ci≤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 ) f(i,j,k,c) f(i,j,k,c)这里的ij表示当前的坐标k表示当前取到了多少个c表示取到物品的数值确保其是递增的。他的意思就是从七点走到ij取了k件物品最后一个物品的价值是c的所有合法方案的集合
对于这个集合如何进行状态计算就是如何进行状态划分因为这个题目的状态非常多就需要逐步分析就像剥洋葱一样一层一层细分第一层是按照位置分分别从上向下走和从左向右走两种第二层是按照第ij个物品是否取得划分那么对于取的情况下对于每一个上一个物品的数值是多少再次进行划分
我们逐步分析每一种情况的状态计算具体是什么
对于从上往下的不取的情况 f ( i , j , k , c ) f ( i − 1 , j , k , c ) f(i,j,k,c)f(i-1,j,k,c) 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,1,w(1,1)1 f(1,1,1,w(1,1)1如果不选择第一个位置的数字就是 f ( 1 , 1 , 0 , − 1 ) 1 f(1,1,0,-1) 1 f(1,1,0,−1)1当然这里的-1是不合法的我们可以给所有的权值加1即可
示例代码
#includeiostream
#includecstring
#includealgorithm
using namespace std;const int N 55,MOD1000000007;int n,m,k;
int w[N][N];
int f[N][N][13][14];int main()
{cinnmk;for(int i1;in;i){for(int j1;jm;j){cinw[i][j];w[i][j];}}// 初始化f[1][1][1][w[1][1]] 1; // 表示选择第一个数是一类方案f[1][1][0][0] 1; // 表示不选第一个数是一类方案for(int i1;in;i){for(int j1;jm;j){if(i1j1) continue; // 表示11位置已经初始化过了for(int u0;uk;u){for(int v0;v13;v){int val f[i][j][u][v]; // 起别名方便表示val (valf[i-1][j][u][v])%MOD; // 表示不选择这个数val (valf[i][j-1][u][v])%MOD;if(u0vw[i][j]) // 如果选择{for(int c0;cv;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 i0;i13;i) ans (ans f[n][m][k][i])%MOD;coutans\n;return 0;
}
