当前位置:首页 » 《随便一记》 » 正文

[蓝桥杯]地宫取宝_m0_51955470的博客

20 人参与  2021年03月09日 09:43  分类 : 《随便一记》  评论

点击全文阅读


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

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

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

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

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

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

输入格式
第一行 3 个整数,n,m,k,含义见题目描述。

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

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

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

数据范围
1≤n,m≤50,
1≤k≤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

解题思路:
首先我们定义dp[i][j][cnt][k]表示小明从左上角走到(i,j)拿了cnt个物品总价值为k的走法,在这道题当中价值的范围为(0,12),意思就是在地图的各个点的物品都有可能价值是0,所以我们在读入数据的时候,将每个数据都+1,这样价值的范围就变成了(1,13),方便我们考虑初始化问题,然后我们想想关系表达式,在这个点可以取或者不取,不取的话,代码如下:

dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i - 1][j][cnt][v]) % MOD;
dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i][j - 1][cnt][v]) % MOD;

这里要分开写,而且结果要%MOD,不然会爆数据,然后小明每次取的物品比前面的物品都要大,然后,如果这个点的物品能取,一定符合:
这个点物品的价值等于我们dp[i][j][cnt][k]中的k值,而且如果取物品,那么cnt一定大于0,然后我们要考虑怎么初始化,在起点,小明有可能拿这个物品,也有可能不拿这个物品,所以不拿就是dp[1][1][0][0] = 1,拿这个物品dp[1][1][1][w[1][1]]

代码如下:

#include <iostream>
using namespace std;
const int N = 55;
const int MOD = 1000000007;
int dp[N][N][15][15];
int w[N][N];
int n, m, k;

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]++;
		}

	dp[1][1][0][0] = 1;
	dp[1][1][1][w[1][1]] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			for (int cnt = 0; cnt <= k; cnt++)
				for (int v = 0; v <= 13; v++) {
					dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i - 1][j][cnt][v]) % MOD;
					dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i][j - 1][cnt][v]) % MOD;

					if (cnt > 0 && w[i][j] == v) {
						for (int s = 0; s < v; s++) {
							dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i - 1][j][cnt - 1][s]) % MOD;
							dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i][j - 1][cnt - 1][s]) % MOD;

						}
					}
				}

	int res = 0;
	for (int i = 0; i <= 13; i++) {
		res = (res + dp[n][m][k][i]) % MOD;
	}

	cout << res << endl;
	return 0;

}

点击全文阅读


本文链接:http://m.zhangshiyu.com/post/16253.html

小明  物品  宝贝  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1