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

技术
©2019-2020 Toolsou All rights reserved,
[数据结构]八大排序算法(C语言)总结G1垃圾收集器面试题Android中使用微信H5支付时支付结果刷新问题32-jdbc工具类大学里要参加竞赛吗?都有哪些竞赛可以参加?震惊!!C++居然可以发出声音!C语言之链表入门(超详解)Java实现一个疫情人数管理系统如何用python实现斐波那契数列的前100个MyBatis循环Map(高级用法)