前言

蓝桥杯官网：蓝桥杯大赛——全国大学生TMT行业赛事
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第六讲：简单dp【习题】

本篇博客所包含习题有：
👊地宫取宝
👊波动数列

简单dp【例题】见博客：蓝桥杯第六讲–简单dp【例题】

博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！

地宫取宝

本题来源：第五届蓝桥杯省赛C++A/B/C组,第五届蓝桥杯省赛JAVAB/C组

题目要求

题目描述：

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

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

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

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

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

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

输入格式：

第一行 $3$ 个整数，$n,m,k$，含义见题目描述。

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

输出格式：

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

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

数据范围：

$1\le n,m\le 50,$
$1\le k\le 12,$
$0\le Ci\le 12$

输入样例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$ 个宝贝，当前所有宝贝的最大值为 $v$，因为宝贝的价值必须是逐渐递增的，且注意到数据范围中有给到宝贝的价格可以是 $0$，故我们一开始 $v$ 的取值其实应该小于 $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]$

1. 从上面来且不拿 $(i,j)$ 位置的宝贝，则 f[i][j][u][v] += f[i - 1][j][u][v]
2. 从左边来且不拿 $(i,j)$ 位置的宝贝，则f[i][j] += f[i][j - 1][u][v]

如果此时的 $v$ 正好等于 $(i,j)$ 处的宝贝的价格，则我们需要加上所有可以转移到该状态的方案数：即用一个 $for$ 去遍历当拿了$u-1$个宝贝的时候，从上面或者左边转移过来的所有方案。

最终，我们取了 $k$ 个宝贝的时候，因为最高价格的宝贝可以是任何的价格，故我们需要对 $f[n][m][k][i]$ 的所有情况进行一个求和，$i$ 的取值即为 $C_i$ 的范围（注意我们已经令所有的 $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;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
 

波动数列

题目来源：第五届蓝桥杯省赛C++A组,第五届蓝桥杯省赛JAVAA组

题目要求

题目描述：

观察这个数列：

1 3 0 2 -1 1 -2 …

这个数列中后一项总是比前一项增加 $2$ 或者减少 $3$，且每一项都为整数。

栋栋对这种数列很好奇，他想知道长度为 $n$ 和为 $s$ 而且后一项总是比前一项增加 $a$ 或者减少 $b$ 的整数数列可能有多少种呢？

输入格式：

共一行，包含四个整数 $n,s,a,b$，含义如前面所述。

输出格式：

共一行，包含一个整数，表示满足条件的方案数。

由于这个数很大，请输出方案数除以 $100000007$ 的余数。

数据范围：

$1\le n\le 1000,$
$-10^9\le s\le 10^9,$
$1\le a,b\le 10^6$

输入样例：

4 10 2 3

输出样例：

2

样例解释：
两个满足条件的数列分别是 2 4 1 3和7 4 1 -2。

思路分析

我们来逐步分析本题：我们的操作只有加上一个 $a$ 或者减去一个 $b$，我们用 $d_1$ 去代表 $a$，用 $d_2$ 去代表 $-b$，即我们每次的操作是对前一个操作要么加上一个 $d_1$，要么加上一个 $d_2$，本题中，我们其实是要求得对于式子：$x+(x+d1)+(x+d1+d2)+...+(x+d1+...+dn-1)=s$，有多少组解，我们对这个实际进行进一步的化简，我们发现只要对于一个 $x$，都需要枚举很多不同的情况，且我们的 $x$ 范围较大，分析难度过于庞大，所以我们想到将 $x$ 进行替换，我们对上述式子进一步化简，下面为化简过程：

$x+(x+d1)+(x+d1+d2)+...+(x+d1+...+dn-1)=s$
$nx+d1(n-1)+d2(n-2)+...+dn-1=s$
$nx=s-(d1(n-1)+d2(n-2)+...+dn-1)$
$x=(s-(d1(n-1)+d2(n-2)+...+dn-1))/n$

即我们最终发现，我们要求的其实就是看看有多少个最终化简结果可以成立，即 $s-(d1(n-1)+d2(n-2)+...+dn-1)$ 可以整除 $n$，即 $s$ 和 $d1(n-1)+d2(n-2)+...+dn-1$ 同余

我们用 $f[i][j]$ 表示只考虑前 $i$ 项，余数为 $j$ 的方案数，故我们的 $f[i][j]$ 可以由两种方法转移得到，一种是 $f[i-1][j-a\ast (n-i)$的余数$]$，一种是 $f[i-1][j+b\ast (n-i)$的余数$]$，最终的 $f[i][j]$ 是这两种情况的和，注意在这里，对于第一种情况： $f[i-1][j-a\ast (n-i)$的余数$]$，$j-a\ast (n-i)$的余数可能是负数，所以我们还需要写一个函数去求得两个数的正余数是多少：

int get_MOD(int a, int b)
{
    return (a % b + b) % b;
}

  

 

  
1
  
2
  
3
  
4
 

以上就是本题的全部分析，可结合代码进一步理解，❗️注： 上述过程中所涉及的所有加法运算需取模。

代码

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

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
 

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/122722116