AcWing 1212. 地宫取宝（DP综合细节题）

本文主要是介绍AcWing 1212. 地宫取宝（DP综合细节题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[题目概述]

X 国王有一个地宫宝库，是 n×m 个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是 k 件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 k 件宝贝。

输入格式

第一行 3 个整数，n,m,k，含义见题目描述。
接下来 n 行，每行有 m 个整数 Ci 用来描述宝库矩阵每个格子的宝贝价值。

输出格式

输出一个整数，表示正好取 k 个宝贝的行动方案数。
该数字可能很大，输出它对 1000000007 取模的结果。

数据范围

1 ≤ n, m ≤ 50,
1 ≤ k ≤ 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

• 分析题目
  本题乍一看和 摘花生那道题很相似，都是两条路，从左边到达和从右边到达，并且他所拿的宝物是一个严格单调递增的序列，又有点最长上升子序列的感觉，因此本题的细节会很多。
  • 先画个图慢慢解释
    
  • 本题的状态表示有四个参数，两个参数是到达的位置，后面两个就是与摘花生那题不一样的地方了，分别表示两个条件，拿的数量和最后拿的一个物品的价值（用于判断严格单调递增用）。
  • 接下来的状态计算就是复杂点了，首先根据从哪个方向到达的可以分成两块，然后每个方向中，到达的这点取不取又可以分成两块。要是取的话，按照我们的划分原则（按照最后一个不同的点划分），又可以根据上一个取得值是多少最多划分为13块。这样我们的分析就结束了，接下来就是代码的部分
• 完整代码
  • 参数范围的说明。
    在进行初始化时，也就是第一个点取与不取。不取时，我们的最后一个参数c应该是比0还小，那么就定为-1，所以c 的 范围应该是 -1~12，但因为我们的索引只能取非负数，就需要给每个价值都加1，所以这个初始化的 c 为0，f[1][1][0][0] = 1;

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;const int N = 55, MOD = 1000000007;
int n, m, k;
int w[N][N], 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 ++) {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 res = 0;for (int i = 0; i <= 13; i ++)res += f[n][m][k][i];cout << res << endl;return 0;
}

• 本题的分享就结束了，此题对于其他他来说比较难理解，需要深入思考一下
  有问题的小伙伴可以发在评论区，记得点赞关注加收藏！

这篇关于AcWing 1212. 地宫取宝（DP综合细节题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---