前言
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第六讲：简单dp【习题】
本篇博客所包含习题有：
👊地宫取宝
👊波动数列
简单dp【例题】见博客：蓝桥杯第六讲–简单dp【例题】
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
地宫取宝
本题来源：第五届蓝桥杯省赛C++A/B/C组,第五届蓝桥杯省赛JAVAB/C组
题目要求
题目描述：
输入格式：
输出格式：
数据范围：
输入样例1：
2 2 2
1 2
2 1
输出样例1：
2
输入样例2：
2 3 2
1 2 3
2 1 5
输出样例2：
14
思路分析
本题其实既包含了我们在 蓝桥杯第六讲–简单dp【例题】 讲到的摘花生一题，又包含了最长上升子序列一题，可以说是两题的结合强化版，建议读者先去掌握这两道题目，然后再来看本题。
我们先来讨论本题需要几维的数组：观测了本题的数据范围不难猜到，本题的维度可能很大：首先由摘花生一题我们需要有两维的坐标，根据最长上升子序列，我们需要有一维的值记录子序列的最后一个数字是多少，最后因为本题需要恰好取 k 个宝贝，故我们还需要有一维来记录当前取了几个宝贝，这样，一个四维表示就被定义出来了：f[i][j][u][v]：当前位于 ( i , j ) 位置上，当前已经拿了 u 个宝贝，当前已经拿了 u 个宝贝，当前所有宝贝的最大值为 v ，因为宝贝的价值必须是逐渐递增的，且注意到数据范围中有给到宝贝的价格可以是 0 ，故我们一开始 v vv 的取值其实应该小于 0 ，如可以定义为 − 1 ，然而数组是不可以出现 − 1 这样的下标的，故我们可以定义为 0 ，然后让所有的宝贝价格都 ++
对于初始值的定义：站在 ( 1 , 1 ) 位置时，如果不拿东西是一种状态，此时为f[1][1][0][0] = 1;，拿东西是一种状态，拿东西则必然拿的是(1,1) 这个位置的东西，即：f[1][1][1][w[1][1]] = 1;，接下来为四重循环：循环行，列，当前拿着的宝贝数，当前拿着宝贝的最大价格：对于每一个新的情况，我们首先分为两部分进行考虑：从上面来的还是从左边来的，此时的状态为：f [ i ] [ j ] [ u ] [ v ]
- 从上面来且不拿 ( i , j ) 位置的宝贝，则
f[i][j][u][v] += f[i - 1][j][u][v] - 从左边来且不拿 ( i , j ) 位置的宝贝，则
f[i][j] += f[i][j - 1][u][v]
如果此时的 v vv 正好等于 ( i , j ) 处的宝贝的价格，则我们需要加上所有可以转移到该状态的方案数：即用一个 f o r去遍历当拿了u − 1个宝贝的时候，从上面或者左边转移过来的所有方案。
最终，我们取了 k 个宝贝的时候，因为最高价格的宝贝可以是任何的价格，故我们需要对f[n][m][k][i]的所有情况进行一个求和，i 的取值即为Ci的范围（注意我们已经令所有的 C i + 1 )
❗️注： 上述过程中所涉及的所有加法运算需取模。
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 55, MOD = 1000000007; int w[N][N]; int f[N][N][13][14]; int main() { int n, m, k; 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][0][0] = 1; f[1][1][1][w[1][1]] = 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 = (res + f[n][m][k][i]) % MOD; cout << res << endl; return 0; }
波动数列
题目来源：第五届蓝桥杯省赛C++A组,第五届蓝桥杯省赛JAVAA组
题目要求
题目描述：
输入格式：
共一行，包含四个整数 n , s , a , b 含义如前面所述。
输出格式：
数据范围：
输入样例：
4 10 2 3
输出样例：
2
样例解释：
两个满足条件的数列分别是 2 4 1 3和7 4 1 -2。
思路分析
int get_MOD(int a, int b) { return (a % b + b) % b; }
以上就是本题的全部分析，可结合代码进一步理解，❗️注： 上述过程中所涉及的所有加法运算需取模。
代码
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 1010, MOD = 100000007; int f[N][N]; // 只考虑前i项，余数为j的方案数 int get_MOD(int a, int b) { return (a % b + b) % b; } int main() { int n, s, a, b; cin >> n >> s >> a >> b; f[0][0] = 1; for (int i = 1; i < n; i ++ ) for (int j = 0; j < n; j ++ ) f[i][j] = (f[i - 1][get_MOD(j - a * (n - i), n)] + f[i - 1][get_MOD(j + b * (n - i), n)]) % MOD; // s可能为负数 cout << f[n - 1][get_MOD(s, n)] << endl; return 0; }
