蓝桥杯国赛十大必备技能——炎之呼吸.叁之型.动态规划

文档中心

🔔燃烧心灵的炎，照亮动归的光

- 💓关于动态规划的小阐述
- 💓壹 - 试题算法提高夺宝奇兵
- - 🌱题目描述
  - 🌴解题报告
  - 🌵参考代码(C++版本)
- 💓贰 - 试题历届试题数字三角形【第十一届】【省赛】【C组】
- - 🌱题目描述
  - 🌴解题报告
  - 🌵参考代码(C++版本)
- 💓叁 - 试题历届真题波动数列【第五届】【省赛】【A组】
- - 🌱题目描述
  - 🌴解题报告
  - 🌵参考代码(C++版本)
- 💓肆 - 试题历届真题地宫取宝【第五届】【省赛】【A\B\C组】
- - 🌱题目描述
  - 🌴解题报告
  - 🌵参考代码(C++版本)
- 💓伍 - 试题历届真题调手表【第九届】【决赛】【B组】
- - 🌱题目描述
  - 🌴解题报告
  - 🌵参考代码(C++版本)
- 💓陆 - 试题历届真题砝码称重【第十二届】【省赛】【A/B/C组】
- - 🌱题目描述
  - 🌴解题报告
  - 🌵参考代码(C++版本)
- 💓柒 - 试题历届真题包子凑数【第八届】【省赛】【A/B组】
- - 🌱题目描述
  - 🌴解题报告
  - 🌵参考代码(C++版本)
- 💓捌 - 试题历届真题二进制问题【第十二届】【决赛】【B组】
- - 🌱题目描述
  - 🌴解题报告
  - 🌵参考代码(C++版本)
- 💓玖 - 试题历届真题密码脱落【第七届】【省赛】【A组】
- - 🌱题目描述
  - 🌴解题报告
  - 🌵参考代码(C++版本)
- 💓拾 - 试题历届真题游园安排【第十一届】【决赛】【A/B组】
- - 🌱题目描述
  - 🌴解题报告
  - 🌵参考代码1——dp 70分(C++版本)
  - 🌵参考代码2——贪心 + 二分 100分(C++版本)
- 💓拾壹 - 试题历届真题生命之树【第六届】【省赛】【B组】
- - 🌱题目描述
  - 🌴解题报告
  - 🌵参考代码(C++版本)
- 💓奥义 - - 第十二届蓝桥杯 C/C++A组回路计数
- - 🌱题目描述
  - 🌴解题报告
  - 🌵参考代码(C++版本)
- 💓 总结
- 💓 关于备战的一点建议

友友们好(^-^)🌹🌹🌹，我是杨枝，一枚在算法领域迈步的呆萌的博主呀~
目前还是一只纯纯的菜汪🐶。典型的又菜又爱闹那种👀，做不好很多事，说不好很多话，写题还总不Ac😅,还在努力还在前进👣。
因为了，你们对我来说都是是独一无二的呀💓。在点开这篇文章的那一刻，我相信，我们之间相互需要彼此啦🌹🌹
时刻谨记：认真写算法，用心去分享。不负算法，不误卿。感谢相遇（＾㉨＾）。

蓝桥杯的十种呼吸法是笔者结合自己的学习筛选出来的十个知识点。本着像看漫画一样了解算法原理。当日后自己确实遇到相关的习题了，可以再回头结合着我的题解报告来加深理解并掌握。

往期精彩

壹	🔖蓝桥杯十大常见天阶功法——水之呼吸.壹之型.递归
贰	🔖蓝桥杯十大常见天阶功法——虫之呼吸.贰之型.二分
叁	🔖 蓝桥杯十大常见天阶功法——音之呼吸.肆之型.模拟

炼狱先生

悄悄说一句闲话：只想含着泪水向时刻面带微笑的大哥递一束花花。

也深深的记住了他临终前的这席话:时间的流动不会为我们停止，时间也不会陪伴我们承担悲伤。燃烧这颗内心吧，要紧牙关向前迈。

支撑我整个叁之型写完的精神动力就是炼狱大哥这席话了，因为我自己也很笨吧，学什么都很慢(一道DP要写四个小时+)。
我自己是三月7号着手写的动态规划，结果今天才更出来(我搜索都快写完了…)，被动态规划卡了很久，也想放弃，也想摆烂，但是时间不会跟着我摆烂，咬紧牙关，终究还有有点眉目了。

要紧牙关向前迈

💓关于动态规划的小阐述

动态规划的解决方式目前其实还蛮多的，比如李煜东老师的《算法竞赛进阶指南》是从决策、转移方向思考的。

Carl的《代码随想录》中是走的五部曲(因为我没有pdf，就手动打吧~)
1、确定dp数组（dp table）及下标的含义
2、确定递推公式
3、初始化dp数组
4、确定遍历顺序
5、举例推导dp数组

不管黑猫白猫了，只要能Ac的，都是好喵喵~

在这里插入图片描述

我自己是acwing门下的一只菜狗，在各位师兄师姐们前面献丑一下了~
将咱们可爱的闫式DP分析法拿出来展示一下。

听闫总讲课说，动态规划可以理解为对暴力的优化。
因为暴力是逐个逐个的处理每种情况，可想而知，其中存在大量的重复情况。动态规划就是将一些相似的情况化零为整了。

举个栗子，咱们处理地图类型的动态规划的时候，我们就只关心上一步是从左边走过来的，还是上面走过来的，从起点到当前这个点中的路径，无论是走了一个弯儿，还是走的直线，还是走了一个爱心，都算出一种类型来处理。

总的来说，就可以得到师兄总结的这张DP分析图了，感谢师兄🌹🌹🌹

在这里插入图片描述

闲话也不多说啦，无限列车的时候，炼狱大哥也是没有说什么闲话，直接就和下弦之一魇梦已经三哥打起来了。

💓壹 - 试题算法提高夺宝奇兵

线性动态规划模型——经典数字三角形的翻版

🌱题目描述

题目 1514: 蓝桥杯算法提高VIP-夺宝奇兵

题目 1514: 蓝桥杯算法提高VIP-夺宝奇兵

🌴解题报告

注意最大数目，看到这个，潜意识就可以把这个题归纳到最优解的问题中了。

动归问题其实可以理解为是暴搜的优化，暴搜是把所有的状态，逐个逐个的进行处理，存在太多的重复的情况，但是动态规划则是将相同的情况归纳为一个集合。

记住这个一种线性DP的模型。它的背景是数字三角形，可能是大多数学动态规划的小伙伴的启蒙题目了。
蓝桥杯国赛十大必备技能——炎之呼吸.叁之型.动态规划

观察这个三角形，对于每个点，它是可以从左上方转移过来，也可以从右上方转移过来。

动态规划的本质了，说直白一点，不整高大上的概念，有点类似于一个递推的过程。
那么我们在划分状态的时候可以将，得到当前状态的最后一个不同点作为划分的依据。
因为是递推，下一个状态的时候，也是如此与考虑，那么整个过程就自底向上的将问题逐渐解决了。

闫式DP分析法：
1、状态表示
集合f[i,j]表示的是从顶点走到(i,j)这个点，其路径上的总和。

集合存的是一个数字，那么最终落实下来，这个数字就被称为集合的属性，这里存的是总和的最大值。

2、状态计算
状态计算是化整为零的过程，将已经划分的集合，处理为一些相似的状态，从而实现分而治之的效果。划分的依据就是上文说的最后一个不同点。

将上述文字做成一张图，就是一张这种效果的闫式DP分析图：
数字三角形

可能有小伙伴不太清楚，这个状态转移方程怎么就出来了呢？

因为，首先我们整体是一个归类的思想，所有从顶点走到图示中(4,2)这点的方案，算作一个集合。
无论是走的7->3->8->7还是的7->8->1->7，都是看做同一个类。

对这个类处理的时候，因为它们最后都肯定会走到(4,2)这个点。
这里就又出现了一个之后文章会反复提起的一句话：把全班分数整体减10分，第一名还是第一名，同样，我们先将(4,2)剔除，就可以很清晰处理最后一个不同点——是从左上转移过来还是右上转移过的。处理好了，补加上这个点

🌵参考代码(C++版本)

#include #include #include using namespace std;const int N = 510,INF = 1e9;int a[N][N];int f[N][N];int n;int main(){    scanf("%d",&n); //输入    for(int i = 1; i <= n;i++)  for(int j = 1; j <= i;j++) cin >> a[i][j];     //初始化数组为负无穷，注意左边边界的空白和右边边界的空白也要初始化的    //比如(2,2)位置的8，因为是集合的思想，它也可能从右上转移过来    //但是那儿实际是没有数据的，因此处理为负无穷    for(int i = 1; i <= n+1;i++)     for(int j = 0; j<=i+1;j++) f[i][j] = -INF; //开始DP    f[1][1] =  a[1][1];    for(int i = 2; i <= n;i++)   for(int j = 1;j <= i; j++) f[i][j] = max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]); //枚举最后一行，找到最大值    int res = -INF;    for(int i = 1;i <= n;i++)  res = max(res,f[n][i]); cout << res <<endl;    return 0;}

💓贰 - 试题历届试题数字三角形【第十一届】【省赛】【C组】

经典线性DP——数字三角形进阶

🌱题目描述

试题历届试题数字三角形【第十一届】【省赛】【C组】

原题传送门

🌴解题报告

大概读完这个题，看到那种熟悉的图，可能小伙伴可能想说，怎么放了一个一模一样的题目?

在这里插入图片描述

小伙伴们再细细品读这个可爱的题，它是有坑的…
相比于常规的数字三角形，它说：此外，向左下走的次数与向右下走的次数相差不能超过1。

因为自己也十分的菜，第一次看到这个限制的想法是自己用两个数记录向左走和向右走的。但是发现反而把自己绕糊涂了

在这里插入图片描述

一个小小的脑筋急转弯

正是因为这个小小的限制，反而也成就了这个题。

因为向左下走的次数与向右下走的次数相差不能超过1，那么整个路线从三角形的顶点开始，那么一路下来都是均匀的。

即：
当最后一层是偶数个数的时候，一定是落在最中间的两个数中的一个上；当最后一层是奇数个数，一定是落在中中间的那一个位置上。

所以我们只需要按照数字三角形的常规思路走，最后依旧最后一行的情况，找到相应的数据，听起来其实有点哈希的思想在里面的，先预处理，最后用 $O (1)$ 实现查找。

那么我就不重复的进行状态表示和状态计算的分析了，直接将DP分析图放上了。

数字三角形

🌵参考代码(C++版本)

#include #include #include #include using namespace std;const int N = 110,INF = 0x3f3f3f3f;int a[N][N];int f[N][N];int n;int main(){cin >> n;for(int i = 1; i <= n;i++)for(int j = 1; j <= i;j++) cin >> a[i][j];//初始化for(int i = 1; i <= n+1;i++)for(int j = 1; j <= i+1;j++)f[i][j] = -INF;f[1][1] = a[1][1];//开始DPfor(int i = 2;i <= n;i++)for(int j = 1; j <= i;j++)f[i][j] = max(f[i-1][j-1]+a[i][j] , f[i-1][j]+a[i][j]);int ans = 0;//输入最后一排的个数是偶数，那么中间两个选if(n % 2 == 0) ans = max(f[n][n/2],f[n][n/2+1]);//最后一排是奇数，那么就输出中间位置上的数据else ans = f[n][n/2+1];cout << ans << endl;return 0;}

💓叁 - 试题历届真题波动数列【第五届】【省赛】【A组】

组合类动态规划+掌握取模

🌱题目描述

题目描述
原题传送门

🌴解题报告

一、题意理解

题目抛出的疑问是让咱们求这种数列的个数：
栋栋对这种数列很好奇，他想知道长度为 n 和为 s 而且后一项总是比前一项增加a或者减少b的整数数列可能有多少种呢？

其实是可以理解为枚举这n个数，用它们来构造数列。

找到一个整数作为数列起点，对它进行 $n - 1$ 次的增加 $a$ 或者减少 $b$ 的操作，最后这串数列的总和是等于 $s$ 的。

那么，最后的提问，相当于问咱们，这种整数的个数有多少个。

二、样例演示

理解了题目表达的意思之后，着手对样例进行一下演示，一般可以从样例的演示从找到一些猫腻的喔~

l露出坏笑

假设这个数列的第一项是 $x$ ，同时 $d i \in$ { $+ a$ ， $- b$ }。

那么这个长度为 $n$ 的序列的所有项应该是： $x , x+d_1 , x+d_1+d_2,...,x+d_1+d_2+...+d_{n-1}$ 。将这 $n$ 项相加起来，就可以得到总和 $s$ 。

经过整理，就可以得到如下式子：

$s = n*x + (n-1)*d_1 + (n-2)*d_2 +(n-3)*d_3 + ... +d_{n-1} ——①式$ 。

咱们之前在题意理解中分析了，是 $x$ 经过运算得到一串数据。

那么咱们可以通过①式得到可以求出 $x$ 的②式

$\normalsize x = \frac{s-((n-1)*d_1 + (n-2)*d_2 +(n-3)*d_3 + ... +d_{n-1} )}{n} ——②式$

三、综合分析

因为题目中说了 $x$ 是整数。

那么 $s-((n-1)*d_1 + (n-2)*d_2 +(n-3)*d_3 + ... +d_{n-1} )$ 的结果称为result，应该是 $n$ 的倍数。即，result % n == 0。

进而可以推导出来：

$s$ % $n$ == $n-1)*d_1 + (n-2)*d_2 +(n-3)*d_3 + ... +d_{n-1} )$ % $n$ 。因为取模之后余数相同，所以也常称为同余

到这里了，答案离我们越来越近了。

拿捏了

此时的意思，只要我们能够找到满足 $n-1)*d_1 + (n-2)*d_2 +(n-3)*d_3 + ... +d_{n-1})$ 的总和模 $n$ 以后的余数是的 $s$ % $n$ 的结果的数量。

四、闫式DP分析

结合着理解，这是一个，依旧是从集合的角度去思考如何表示状态和锁定目标。

状态表示：f[i][j]表示考虑前 $i$ 项，总和除以 $n$ 得到的余数是 $j$ 的方案的一个集合。

最终目标：最后求得是 $f [n - 1] [s$ % $n]$ 的值

波动数列

🌵参考代码(C++版本)

#include #include #include using namespace std;const int N = 1010,MOD = 100000007;int n,s,a,b;int f[N][N];//集合的意思是，只考虑前i项，且当前的总和除以n的余数是j的方案的集合的数量//因为要涉及到取余这个操作，在C++中，负数取余得到的是负数，但是数组的索引下标不能为负int get_mod(int a, int b){    //假如a是-13，b是4。a除以b的正余数应该是1    //a % b = -1。    //a % b + b = 3    //此时再取模得到的就是一个正余数了    return (a % b + b) %b;}int main(){    cin >> n >> s >> a >>b; //初始化    f[0][0] = 1;//也只有f[0][0]是有意义的，其他的是不合法的。 //根据题意来，长度为n的序列：x,x+d1,x+d2,x+d3,…,x+dn−1    //可以看出是d是从1执行到n-1    for(int i =1; i < n;i++) for(int j = 0; j < n;j++)//余数的范围是从0~n-1 f[i][j] = (f[i-1][get_mod(j- a * i,n)] + f[i-1][get_mod(j + b * i,n)]) % MOD; cout << f[n-1][get_mod(s,n)] << endl;    return 0;}

大致的了解到一些动态规划的形式之后，咱们来弄点综合一点的练习吧~
在这里插入图片描述

💓肆 - 试题历届真题地宫取宝【第五届】【省赛】【A\B\C组】

地图类型的——再听y总描述，待会调整描述的顺序+从数据范围推算法

🌱题目描述

$试题历届真题地宫取宝【第五届】【省赛】【A\B\C组】$
原题传送门

🌴解题报告

1、题意理解

看到题目的背景是一个矩阵里取东西，只能向下或者向右走，有点线性动态规划的感觉了。这种乍一看的感觉，就是平时刷题积累的经验了

我们可以很清晰的get到第一个限制：

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

蓝桥杯国赛十大必备技能——炎之呼吸.叁之型.动态规划
继续读题，可以发现第二个限制

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

这句话的意思了，翻译过来就是，小明每次拿东西，只能拿比当前价值大的东西，也就是按照递增的顺序拿。

继续读题，瞬间就看到了第三个限制：

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

题目的最后，就是让我们在拿k件物品的情况下，小明有多少种走法。

重要技巧——从数据范围设计算法

根据线性动态规划那儿，可以先定出两维 $f [i, j]$ 。
为了保证是递增的顺序，要存下当前取的最后一个数是哪个数，那么就需要两维 $(x, y)$ 。
但是因为数据范围很小，就可以直接记录当前这个数，具体是多少，不需要使用两维来映射了。

再加上限制是 $k$ 。那么整体的状态，应该是用4维来表示: $f [i, j, k, c]$ 其计算量是 $50 * 50 * 12 * 13$
约等于40万的样子。 $C + +$ 一秒是进行 $10^7$ ~ $10^8$ 次

大约还有25次的计算量，这里应该是用于状态转移的计算了。那么整体框架，应该是五重循环。

2、梳理状态表示

f [i, j, k, c]表示的是从起点 $(1, 1)$ 开始出发，走到 $(i, j)$ 这个位置，拿了k件物品手中最大价值是 $c$

3、状态转移分析

最后一步是从上往下走的，可以分为取和不取。
最后一步是从左往右走的，也可以分为取和不取。

不取的情况比较容易分析，再分别加上数量 $k$ 以及手中最大价值 $c$ ，因为没有取，所有 $k$ 和 $c$ 都是不用变化的。即得：

从上到下不取是 $f [i] [j] [k] [c]$ += $f [i - 1] [j] [k] [c]$

以及

从左到右不取是 $f [i] [j] [k] [c]$ += $f [i] [j - 1] [k] [c]$

取的情况就稍微有点棘手了。

如果要取当前的宝藏，需要满足当前的状态 c ==当前位置的宝藏价值，这是因为限制2,因此如果取完宝藏以后，必须满足最大的价值为c。然后我们只需要每次枚举的时候，加上比c小的部分的方案就好了。

那么：

从上到下取是： $f [i] [j] [k] [c]$ += $f [i - 1] [j] [k - 1] [小于 c 的数]$

以及

从左到右取是： $f [i] [j] [k] [c]$ += $f [i] [j - 1] [k - 1] [小于 c 的数]$

结果统计就是将各个集合的个数全部加起来了。

将文字提炼一下，闫式DP分析图就可以拿捏出来了

通过这个图，我们可以看到，这回的DP分析是稍微有点复杂的了。

4、初始化

对于起点(1,1)，咱们也是要进行取和不取两种状态的处理

倘若取：

$f [1] [1] [1] [w [1] [1]]$ = 1。也就是，从(1,1)走到(1,1)，手中有一个宝藏，它的最大价值是 $w{_1,_1}$ 的方案数有1个

倘若不取：

需要初始化为 $f[1][1][0][比给的价值C_i还要小的价值]$ ，因为 $0<=C_i<=12$ ，比给定的 $C_i$ 还小，就只有考虑负数了，但是数组中的索引是不能取负数的。
就可以采用将 $C_i$ 整体+1的思想,那么 $C_i$ 的范围就变成了 $1<=C_i <=13$ ，此时就可以用取0来表示 $比给的价值C_i还要小的价值$

给坚持看到这儿的小伙伴擦擦泪水😭😭😭
在这里插入图片描述

🌵参考代码(C++版本)

#include #include #include #include using namespace std;const int N = 55,MOD = 1000000007;int n,m,k;int w[N][N];//存放每个格子的宝贝的价值int f[N][N][13][14];//数组或者说是集合f维护的是n行m列,在拿k个物品的情况下，且最后一件物品是c的状态的数量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]都加1的操作，但是我没有太能get到     w[i][j] ++; } //处理假如只有(1,1)这个位置    //假如(1,1)这里拿了    f[1][1][1][w[1][1]] = 1;    //假如(1,1)这里不拿;    f[1][1][0][0] = 1; //进入DP环节    for(int i = 1; i <= n;i++) for(int j = 1; j <= m;j++) {     if(i ==1 && j == 1) continue;     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;}

看我画了这么几张闫式DP分析图，会不会有小伙伴潜意识中逐渐以为，做动态规划一定要画闫式DP分析图了？我当初就是这种的想的，太呆萌了😭😭😭
在这里插入图片描述

闫总说过，动态规划的难度确实就在那儿放着的，就像要走到五楼，确实要一点一点向五楼迈，闫式DP分析可以说帮我们搭建了一个梯子，让咱们省力一些了，不用直接蹦上去了。

还有就是有些题目的状态转移方程比较明显，或者友友们达到一定修为了，直接可以一眼将状态怎么转移的想清楚，那么此时就不用画图了wo~

举个不好听的例子吧，很多博客讲动态规划都是斐波那契数列和跳台阶。我是真的不知道这两个直接可以三秒看出转移方程的题为什么要被这么多博主反复赘述

在这里插入图片描述

💓伍 - 试题历届真题调手表【第九届】【决赛】【B组】

一、记录是因为防止思维定势，闫式DP分析是帮助分析，不是说一定要画它。
二、它是有点类似于完全背包，但是和完全背包还是有点区别，比完全背包更单纯

🌱题目描述

历届真题调手表【第九届】【决赛】【B组】
原题传送门1
原题传送门2

🌴解题报告

一、意识培养

当看到找最优解，而且给的信息是可以无限用的，然后让咱们找到凑出某个数值的方案的时候，就可以向着完全背包的方向思考，比较让人安心的是，这个题感觉是伪完全背包，只是用到其中的一点点思想

二、温习完全背包

完全背包最淳朴的版本是这种的：

完全背包

对其进行状态表示和状态计算的分析：

状态表示：

集合：f[i][j]表示从i个物品进行选择，总体积不超过j的方案的集合
属性：属性大多数是最大值max

状态计算：

状态计算对应的是对咱们所定义的集合f[i][j]的划分过程，划分依据是最后一个不同点。
对于完全背包而言，最后一个不同点就是当前这物品，它被用了多少次才凑出这个总体积 $j$ 的。

完全背包

小伙们也可以看这张出上述步骤总结出来的闫式DP分析图，稍显凌乱了
完全背包

三、降服本题

这道题中，+1和+ $k$ 是可以无限用的，对比起标准完全背包，它只有两个物品在无限用，标准完全背包的状态转移方程就不适用了，这会困扰咱们吗？不，这让题变得更简单了。

闫式DP分析

状态表示：

集合：f[i]表示从0分钟调整到i分钟，需要调整多少次
属性：最小值

这个题有点逗，它问题的意思是让咱们求一批最小调整方案中的最大值…离谱
在这里插入图片描述

状态计算：

要么从+1转移过来，要么从+k转移过来，那么还原回到(i-1)的状态的时候，只需要扣除相应的值，同时补上这次调整，也就是+1。
写到这儿，我感觉它又像01背包了，这个题蛮可爱的。

f[i] = min(min(f[(i-1)%n], f[(i+n-k)%n]), f[i])+1;

最后遍历得到的方案，得到答案。

🌵参考代码(C++版本)

#include #include #include using namespace std;long long n, k, j;int f[100010];int main(){  cin >> n >> k;  //初始化，默认一次是一分钟，那么现在是多少次，就是多少分钟  for(int i = 0; i < n; i++)  f[i] = i;   //进行一步预处理，找到每个时间点，一次走k下，所有需要的最少次数  for(int i = 1; i < n; i++)  {    j = i*k % n;    f[j] = min(f[j], i);  }    //因为f[0]不用处理了，从2开始枚举  for(int i = 2; i < n; i++)  f[i] = min(min(f[(i-1)%n], f[(i+n-k)%n]), f[i])+1;    int maxv = 0;    for(int i = 1; i < n; i++)  maxv = max(maxv, f[i]);    cout << maxv << endl;    return 0;}

既然掌握了完全背包，来看看蓝桥中也是比较常见的01背包吧。

💓陆 - 试题历届真题砝码称重【第十二届】【省赛】【A/B/C组】

变型的01背包

🌱题目描述

试题历届真题砝码称重【第十二届】【省赛】【A/B/C组】

原题传送门

🌴解题报告

看到题目中说到让咱们寻找一个最优解，那么这个时候，可以尝试向着动态规划的方向去思考。

本题是在有限制的情况下进行选择，也就是以背包问题为代表的选择模型。

系统温习背包问题：

背包问题中 $f [i] [j]$ 表示从前 $i$ 个物品中进行选择，在背包容量为 $j$ 的背包中能够存放的物体价值之和的最大值。

对于本题：

状态表示：
集合：集合f[i][j]表示的含义是从前i个砝码中进行选择且总体积为j的所有方案的集合

属性：这个集合所存储的属性是集合是否非空。表示从前i个砝码中选出总重量为j的方案是否存在，可以很明显的看出，是一个bool值。

状态计算：

状态计算对应的是对咱们规定的集合的划分，划分的依据大多是最后一个不同点。

比如本题，最后一个不同点就是当前这个砝码是怎么进行放置：

假如要称重的物品默认放在左边
1、不选当前砝码，即 f[i][j] = f[i-1][j]

2、选择当前砝码来增加称重盘中的重量(即把当前砝码放在右边)，f[i][j] = f[i-1][j-w[i]]

3、选择当前砝码来削减称重盘中的重量(即把当前砝码放在和物品一起)，f[i][j] = f[i-1][j+w[i]]

将如上的步骤进行整理的，那么就可以得到这张闫式DP分析图
砝码称重
同样的，对应一定会选择的砝码i，依旧先采用先剖除它并不会影响整体格局的思想，也就是i-1，对应修改总和j受到的影响。

🌵参考代码(C++版本)

#include #include #include #include using namespace std;const int N = 110,M = 100010;int n,m;int w[N];//存储砝码质量的数组bool f[N][2 * M];//表示状态的数组int main(){    cin  >> n;//DP环节会有减一的，都建议从1开始获取值    for(int i = 1; i <= n;i++) cin >> w[i],m += w[i]; //初始化，这行代码的意思是，从前0个砝码中选出总和为0的方案是存在的//M 只是都要加的一个偏移量    f[0][M] = true;//枚举n个砝码    for(int i =1; i <= n;i++)    {    //枚举会出现的重量，因为可能为负，所有统计加上了一个偏移量M    for(int j = -m; j <= 2 * m ;j++)    {//情况一：不选当前砝码的集合不是空if(f[i-1][j+M]){f[i][j+M] = true;continue;}if(j - w[i] >= -m &&f[i-1][j- w[i] + M]){f[i][j+M] = true;continue;}if(j + w[i] <= m && f[i-1][j+w[i] + M]){f[i][j+M] = true;}}}//遍历得到的方案，统计结果unsigned long long cnt = 0;//unsigned可用于防止溢出for(int i = 1; i <= m;i++)if(f[n][i+M]) cnt ++;cout << cnt << endl;//printf("%lu",cnt);return 0;}

再系统的看一道背包问题，作为道别吧，蓝桥杯中完全背包和01背包出现得还是挺勤的

💓柒 - 试题历届真题包子凑数【第八届】【省赛】【A/B组】

纯正的完全背包+互质数学规律

🌱题目描述

试题历届真题包子凑数【第八届】【省赛】【A组】

原题传送门

🌴解题报告

感觉这个题，读起来有点拗口，不知道小伙伴们有没有这种感觉了，

通俗来说了，就是包子大叔有很多笼固定数量的包子，比如5个一笼的，9个一笼的。
有无限笼，注意无限这两个字，然后细细品读这句话小明想知道一共有多少种数目是包子大叔凑不出来的。

这句话的意思就是让咱们找到最优解，那么动态规划可以拿出来了，看到无限二字，向着完全背包的方向思考。

对于完全背包状态转移方程通式的获得是经过如下的DP分析以及数学归纳之后的结果，我只是放置在这儿，根据小伙伴们的需求，能理解性的记忆最好。
假如时间吃紧的话也可以直接背下来先用着，以后再回头理解它的时候回会很轻松的

完全背包

本题需要注意的第二个点是一个数学规律：

当两个整数p、q互质时，最大不能组成的整数为 (p-1)(q-1) – 1 ；

当两个整数不互质时，不存在最大不能组成的整数，即最大不能组成的整数为无穷大。

整数间若不互质，最大公因子为d，即每个整数都是d的倍数。

d > 1时，最大不能组成的整数为无穷大。因此，可以先计算出n个整数的最大公因子，若 > 1，则输出INF。

若等于1，则采用动态规划进行分析

状态表示：

集合：集合f[i,j]表示前i个数值的蒸笼凑成的包子数目为j的方案的集合
属性：Bool 也就是说存储的是集合是否为空

状态计算：
依旧是依据最后一个不同点，完全背包中，最后一个不同点就是当前这个物品i选择的数量。可以选0个，也可以选k个。

①、不选当前这笼包子就可以凑出j： f[i-1,j]
②、当前这笼包子要选k个就可以凑出j：f[i-1,j k * v[i]]

因为对于本题的包子而言，就只有探讨数量的，所以对比传统的完全背包，少了一个w[i]

🌵参考代码(C++版本)

#include #include #include #include using namespace std;const int N = 110, M = 10010;//M 是 最多一百种蒸笼，每笼包子最多100个int v[N];bool f[N][M];int n;//判断最大公约数，即欧几里得算法int gcd(int a,int b){return b? gcd(b,a % b) : a;}int main(){//处理输入cin >> n;for(int i  =1; i <= n;i++) cin >> v[i];//根据本题的数学背景。现在要去找到读入的数据的最大公约数int x = v[1];for(int i = 2; i <= n;i++) x = gcd(x, v[i]);//判断最大公约数是否大于1if(x > 1) printf("INF\n");//最大公约数为1，也就说，它们是互质的，那么开始DPelse{//初始化f[0][0] = true;for(int i = 1; i <= n;i++)for(int j = 0; j <= M;j++){if(f[i-1][j]){f[i][j]  =true;continue;}int k = 1;while(j - k * v[i] >= 0){if(f[i-1][j-k*v[i]]){f[i][j] = true;break;}//跳出当前的选择，进行一下个k++;}}long long cnt = 0;//遍历所有组合，输出答案for(int i = 1; i <= M;i++)if(f[n][i] == false) cnt++;cout << cnt <<endl;}return 0;}

到这儿了，DP中比较简单的内容算是告一段落，就像炭炭和猪猪合手解决上弦之一的梦魇。要着手迎战三哥了

在这里插入图片描述

💓捌 - 试题历届真题二进制问题【第十二届】【决赛】【B组】

数位DP——有一定的模板

🌱题目描述

二进制问题

原题传送门

🌴解题报告

我大致看了三个数位DP的题，感觉它对比起其他DP，相对是友好一点的，因为它可以理解为是有一个浅浅的模板的。

数位DP我看的是这位大佬的文章数位dp总结之从入门到模板。但是感觉大佬的排版稍微有点凌乱，我后面再刷几个数位DP的题了，结合大佬的文章，做一期数位DP的博客。

数位dp是一种计数用的dp，一般就是要统计一个区间[le,ri]内满足一些条件数的个数。

所谓数位dp，字面意思就是在数位上进行dp了。数位还算是比较好听的名字，数位的含义：一个数有个位、十位、百位、千位…数的每一位就是数位啦！

之所以要引入数位的概念完全就是为了dp。数位dp的实质就是换一种暴力枚举的方式，使得新的枚举方式满足dp的性质，然后记忆化就可以了。

🌵参考代码(C++版本)

#include using namespace std;typedef long long LL;const int N = 70;int bits[N];LL f[N][N][2];LL n, k;LL dfs(int pos, LL count, int limit){//已经将现有的位数递归完，结束递归    if (pos == -1) return count == k; if (!limit && f[pos][count][limit] != -1) return f[pos][count][limit]; //确定可以枚举的上界    int up = limit ? bits[pos] : 1; LL ans = 0;//在上界范围内枚举    for (int i = 0; i <= up; ++i) ans += dfs(pos - 1, count + (i == 1), i == up && limit);    if (!limit) f[pos][count][limit] = ans; return ans;}int main(){    cin >> n >> k;    int len = 0;    memset(f, -1, sizeof(f));    while (n){ bits[len ++] = n & 1; n >>= 1;    }    cout << dfs(len - 1,0, 1) << endl;    return 0;}

数位DP我暂时还没有完全get到它这个模板的玩法，就稍显粗糙了。

在这里插入图片描述

下面着手去解决蓝桥中更为常见的最长公共子序列和最长上升子序列了

💓玖 - 试题历届真题密码脱落【第七届】【省赛】【A组】

最长公共子序列（LCS）、区间DP

🌱题目描述

密码脱落

原题传送门

🌴解题报告

一、逆向思维

题目要咱们找到的是，原本的一个回文串，掉落几个种子之后，变成了现在的字符串。

结合样例演示：

ABECDCBABC，其中ABC CDCBA可以构成一个回文串，此时的E、B、C是孤零零的。只要将它们配对了，就可以回到原本的形态。

那么这个游戏现在就变成了，找出现在的字符串中最大的回文串，剩下的就是脱落的了。也就是回到最长公共子序列(LCS模型)。

二、闫式DP分析

状态表示——问题问什么，咱们就表示什么

集合：f[i,j]表示从i到j这个区间中，回文子序列的集合

f[i，j]最终要落实到存储一个数上去，这个数就是闫式DP分析中的属性

属性：最大值

状态计算：

状态计算对应的是化整为零，将咱们定义的集合，划分为相似的板块进行处理。
划分的依据大多是去寻找这些状态转移到当前状态时，最后一个不同点。对于区间DP，可以记住一般就是对端点进行处理。

1、两个端点(i,j)都存在的时候，采用先把都有的部分剔除再加上的想法：f[i+1,j-1] + 2

2、只有左端点i在区间中：f[i,j-1]

3、只有右端点j在区间中：f[i+1,j]

4、两个都不在:f[i+1，j-1]

小伙伴们应该可以发现，情况四其实是有部分和情况二和情况三重合了。那咱们现在只需要处理三种状态了。去每种状态中找到最大值。

🌵参考代码(C++版本)

#include #include #include #include using namespace std;const int N = 1010;int f[N][N];char s[N];int main(){    //输入    scanf("%s",s);    int n = strlen(s); //小小的模板了：枚举当前这个区间    for(int len = 1; len <= n;len ++) //枚举左端点 for(int i = 0; i + len - 1 < n;i++) {     //枚举右端点     int j = i + len -1;     if(len == 1) f[i][j] = 1;     else      {  //只有左端点、只有右端点、以及左右端点都没有的情况  f[i][j] = max(f[i+1][j],f[i][j-1]);  //两个端点都有  if(s[i] == s[j]) f[i][j] = max(f[i][j],f[i+1][j-1]+2);     } } printf("%d\n",n - f[0][n-1]);    return 0;}

才接住了三哥的一招空式，现在着手接碎式吧！~

在这里插入图片描述

💓拾 - 试题历届真题游园安排【第十一届】【决赛】【A/B组】

最长上升子序列（LIS）

LIS（Longest Increasing Subsequence）

最长上升子序列一个数的序列 $b_i$ ，当 $b_1$ < $b_2$ < … < $b_S$ 的时候，我们称这个序列是上升的。
对于给定的一个序列( $a_1$ , $a_2$ , …, $a_N$ )，我们可以得到一些上升的子序列( $a_{i1}$ , $a_{i2}$ , …, $a_{iK}$ )，这里1 <= $i 1$ < $i 2$ < … < $i K$ <= $N$ 。
比如，对于序列(1, 7, 3, 5, 9, 4,8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).你的任务，就是对于给定的序列，求出最长上升子序列的长度。

LIS常用的是三种方式（记住）：
算法一：动态规划时间复杂度 $O(n^2)$
算法二：贪心 + 二分时间复杂度 $n l o g n$ 算法三：
动态规划 + 树状数组时间复杂度 $n l o g n$ （暂时还不会）

🌱题目描述

试题历届真题游园安排【第十一届】【决赛】【A/B组】

原题传送门1
原题传送门2

🌴解题报告

这个题直接用 $O(N^2)$ 的时间复杂度的动态规划来做是会因为超时，最终导致只能得到70分。

我直接把代码放这儿吧，可以作为一个练习的参考，要Ac咱就不用它了。

最长子序列的算法板子我是在acwing上学的，就把闫总的题目放置在这儿了

朴素版本时间复杂度 $O(n^2)$	AcWing 895. 最长上升子序列
贪心 + 二分时间复杂度 $O (n l o g n)$	AcWing 896. 最长上升子序列 II

🌵参考代码1——dp 70分(C++版本)

蓝桥杯国赛十大必备技能——炎之呼吸.叁之型.动态规划
就当温习一下朴素版本LIS的模板吧

#include #include #include #include using namespace std;const int N  = 1e6 + 10;string s;int f[N];//存储集合的数组string v[N];//存储人名的数组int main(){//输入cin >> s;int num = 0;//将输入的字符串依据大写，分割为人名存储到数组中for(int i = 0; i < s.length();i++)if(s[i] >= 'A' && s[i] <= 'Z')//当目前这字符是大写的时候{num ++;v[num] = "";//每次用一个空字符串来分割人名v[num] += s[i];}else{v[num] += s[i];//意思当前不是大写，不必进行人名的分割，直接接在现有的字符串数组后面就好}int max_len = 0;//统计最长上升子序列的个数,初始化为0int pos = 1;//记录位置//下面就是标准的最长上升子序列的模板了...for(int i = 1; i <= num;i++){f[i] = 1;//查找人名for(int j = 1; j < i;j++)if(v[j] < v[i]) //如果上一个人名小于第j个人名f[i] = max(f[i],f[j]+1);if(f[i] >= max_len) max_len = f[i],pos = i;}//这个题，假如在不超时的情况下，就是这个路径输出比较棘手string res;for(int i = pos; i >= 1;i--) {printf("if外的f[%d]是%d\n",i,f[i]);if(f[i] == max_len) //利用自己统计出来的最长长度来输出路径{res = v[i] + res;cout <<"当前的res = "<< res << endl;max_len --;}}cout << res << endl;return 0;}

下面着重说一下怎么贪心 + 二分解决这个题。

这里就不手写二分了，直接使用stl库函数中的 lower_bound返回大于等于传入值的第一个元素的位置。

至于贪心的思想了，我们先将所有的游客名处理好，存储到数组中。先将第一个序列name[0]放入集合。

此时开始遍历身下的游客的名字，倘若遇到比当前集合末尾的序列还大的姓名串，就直接放入集合；
倘若现在遍历的姓名串比当前集合末尾的序列要小，那么就把它用替换比它大的第一个姓名串，把它放入集合，同时更新f数组维护的单调子序列长度

总的来说，遇到大的就尾部插入，遇到小的就内部替换，最终的到的就是一个严格上升的序列。

🌵参考代码2——贪心 + 二分 100分(C++版本)

#include #include #include #include #include using namespace std;const int N = 1e6 + 10;string name[N];//存储人名的数组string s;vector<int> f;//f 存储的是每个子序列的最长上升子序列的长度vector<string> str;int main(){//输入cin >> s;//老规格，把字符串按照题目要求分割开int num = 0;for(int i = 0; i < s.length();i++){if(s[i] >= 'A' && s[i] <= 'Z'){if(i!=0) num ++;name[num]  = "";name[num] += s[i];}else name[num] += s[i];}str.push_back(name[0]);f.push_back(1);//遍历分割到的名字for(int i = 1; i <= num;i++){//如果现在这个i所在的串是比已经存储的名字串的最后一个还大if(name[i] > str.back()){str.push_back(name[i]);//加入如当前的串//更新当前动态数组的长度f.push_back(str.size());}else{//当前这个i所在的串是比已经存储的名字串的最后一个小//进入贪心环节//利用二分找到大于等于序列name[i]的第一个元素的位置int pos = lower_bound(str.begin(),str.end(),name[i]) - str.begin();//将这个位置的元素替换为v[i]     str[pos] = name[i];     //更新当前动态数组的长度     f.push_back(pos+1);}}string ans[N];//统计结果  int cnt = 0;//计数器for(int i = num,j = str.size(); j > 0; i--){if(f[i] == j){ans[cnt ++] = name[i];j --;}}//输出获得的姓名串for(int i = cnt -1; i >= 0; i--) cout << ans[i];    return 0;}

在这里插入图片描述

抽刀，再战~

💓拾壹 - 试题历届真题生命之树【第六届】【省赛】【B组】

树形DP

🌱题目描述

试题历届真题生命之树【第六届】【省赛】【B组】
原题传送门

🌴解题报告

树形DP了，本质是不难的，只是假如没有提前接触。不太能想到那个点上去。

一、背景剖析

学数据结构的时候，都应该记得一句话叫做链表是特殊的树。

斜二叉树
同样的，线性DP是把DP在一段类似于链表的、线性的结构(比如数组)上进行。树形DP只是把背景搬到树上来了。

二、解决思路

树形DP是用递归（也可以说是深度优先遍历）解决。也就是每次处理这个树的根，然后递归进去统计这个根的子树的信息。

三、闫式DP分析

状态表示：

集合：f[u]表示在以u为根的子树中包含u的所有连通块的权值的最大值。
属性：最大值

这个题，感觉状态转移方程都没有了…

现在的情况就是这种样子的了，假如有一棵以u为根的子树。想统计这个连通块的最大值，那么只需要保证其每个子树，能够取到最大值就好。

最大值

需要注意的是，因为权值可能为负，因此当出现统计出来的最大值是负数的时候，直接舍弃了…(也就是将最大值置为0)

🌵参考代码(C++版本)

#include #include #include using namespace std;const int N = 100010,M = 2*N;typedef long long LL;int n;int w[N];//树结点的权重int h[N],e[M],ne[M],idx;//邻接表LL f[N];//状态数组//默写使用邻接表构建边的函数void add(int a,int b){    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;}//存一下当前搜的父结点是谁，防止往回搜void dfs(int u, int father){    f[u] = w[u]; //搜一下这个u的儿子    for(int i = h[u];i != -1;i = ne[i])    { int j = e[i]; //如果不是向回搜的 if(j != father) {     //递归进去，并标记当前这个结点是从u下来的     dfs(j,u);     f[u] += max(0ll,f[j]); }    }    }int main(){ scanf("%d",&n);    memset(h,-1,sizeof h);    //读入每个 点的权值    for(int i = 1; i <= n;i++) scanf("%d",&w[i]); //读入每个边的情况    for(int i = 0; i < n-1;i++)    { int a,b; scanf("%d %d",&a,&b); add(a,b),add(b,a);    } //递归搜索    dfs(1,-1); //求最大值    LL res = f[1];    for(int i = 2;i <= n;i++) res = max(res,f[i]); if(res < 0) res = 0;    printf("%lld\n",res); return 0;    }

终是大哥以凡人之躯比肩神明，我以不惧失败之势鏖战动归

在这里插入图片描述

💓奥义 - - 第十二届蓝桥杯 C/C++A组回路计数

状态压缩DP

🌱题目描述

第十二届蓝桥杯 C/C++A组回路计数

原题传送门

🌴解题报告

看到数据范围很小的小伙伴有没有想过可以使用暴搜来解决了。但是比较扎心的是，虽然数据范围足够小了，假如直接暴搜，运算量是 $22$ $22!$ ，肯定是乎超时的。

咱也不卖关子了，哈密尔顿回路也叫做旅行商问题，因为计算量是十分十分的庞大。假如在考试中遇到了，唯一的选择就是状态压缩动态规划了。

哈密尔顿回路

何为状态压缩？咱不扯不负责的理论了，复杂的理论不能帮助咱们考试Ac
看了Pluto大佬描述的关于状态压缩的话，觉得很到位，就直接摘抄过来了吧：

在这里插入图片描述

状态压缩是怎么回事呢？就是把每一个点的状态抽象到一个二进制数的一位上（就因为这个所以说状压dp题目一般数据不会很大），然后用位运算实现标记状态和查看状态。
状压dp首先要二进制枚举状态，然后找到该状态下走过的点，然后再枚举一下这个点是从那个点走过来的就可以了。

举个直白的例子：当前的状态i的二进制表示为(1101101)，对于当前状态而言，是1的位置就表示走过了，是0的位置就表示没有走过。

友友们可以脑补一下，对于当前的状态i，就是第一栋教学楼走了，第二栋没有走，第三栋走了，第四栋走了…

回到咱们熟悉的闫式DP分析法:

状态表示：
集合：所有从点1走到点j,经过的点的状态为i的集合
题目要统计的是数量，那么
属性：数量Count

状态计算：

记住DP本质其实是一个递推，我们现在需要关心的点就是，我是怎么从其他地方走到这栋教学楼的。

综上所述，就是得到了这个可爱的闫式DP 分析图：
闫式DP分析

🌵参考代码(C++版本)

#include #include using namespace std;typedef long long LL;const int N = 22,M = 1 << N;bool w[N][N];//记录i是否能走到jLL f[M][N];//所有从点1走到点j,经过的点的状态为i的集合//判断是否互质的欧几里得算法gcdint gcd(int a,int b){return b ? gcd(b,a%b):a;}int main(){//处理这21座教学楼的连通情况for(int i = 1; i <= 21;i++)for(int j = 1; j <= 21;j++)if(gcd(i,j) == 1) w[i][j] = true;//初始化，f[2][1] = 1;//枚举这2的21次方种状态//f[i][j]：从 1 走到 j，且经过的点的状态为 i 的方案数//做了一下步优化，可以少进行两次循环了for(int i = 2; i <= M-2;i++)for(int j = 1;j <= 21; j++){//如果到j这栋教学楼的路径，也是属于到i这栋教学楼的一部分if((i >> j) & 1){//枚举当前的j是从1~21中哪栋楼转移过来的for(int k = 1; k <= 21;k++)//记住w[k][j]很重要，因为互质，导致两栋楼是联通的，这种才能实现从k再到jif(i - (1 <<j) >> k & 1 && w[k][j])//i - (1 << j)表示从总状态i中扣除从1到j的状态f[i][j] += f[i - (1 << j)][k];}}LL ans = 0;//遍历这些集合，统计结果for(int i = 2; i <= 21;i++)ans += f[M-2][i];cout << ans << endl;return 0;}

💓 总结

这种图是从蓝桥官方给的近三年知识点总结的pdf中截取的。
在这里插入图片描述

我这篇叁之型差不多将蓝桥中容易出现的动态规划都系统的总结了一遍了。但是可能还是不够全面的，感觉动态规划算是我算法生涯中的三哥吧，无限列车和炼狱第一次邂逅它，苦战。后面在无限城中再遇三哥的时候，我希望我再写动态规划，会更成熟、更精妙，彻底战胜三哥猗窝座吧~

💓 关于备战的一点建议

大致浏览完这篇文章的小伙伴可以发现，这篇文章几乎没有什么概念，定义和晦涩的知识点了，全是实打实的硬仗。

因为动态规划不像最短路、或者搜索会有板子可以背，学它的最好建议是在闫式DP分析的帮助下多去刷，然后就会感觉看到一些题就知道，可以DP，就可以直接秒状态转移方程的感觉的，大家要相信自己呀。

可能有小伙伴说，有些题解博客好糟糕，看着太晦涩了又找不到问题的地方。友友你可以私信问我，但是我因为这个学期加了课程，就挺吃力的。有时候因为我自己能力不够或者我直接被学校里的事儿耽搁了不能及时回复😭😭😭，所以更倾向大家请教这几位博主喔，他们都是我非常钦佩的大佬，私信他们就好喔~

在这里插入图片描述
C/C++

Pluto（算法健将，各类周赛打宝宝级别）	个人主页
泡泡(以大一学籍让无数大四学长自愧不如，正在刷爆洛谷)	个人主页
折叠的小饼干(实力派学姐，温柔耐心~)	个人主页
knao_s（题解绝绝子，除了详细到位，还是详细到位）	个人主页
永遇乐金枪鱼（一位谦虚的大佬，精准把握你题解思路中不对的地方）	个人主页

Java

执梗(带三百人冲刺蓝桥主要负责人，讲题细心，出题尽职尽责🌹)	个人主页
小怂(用最朴素的for、while、if刷爆蓝桥云课，担心不熟悉数据结构影响解题的小伙伴可以多请教他喔~)	个人主页
小羊不会飞(题解常年稳居热榜前八，题解质量经得起检验，为人谦虚耐心)	个人主页
Hydrion-Qlz（西安交大大佬，算法爱好者）	个人主页
小成同学（acwing师兄，刷题健将，考虑问题周全）	个人主页
托马斯—酷涛（Java算法爱好者，对多个方向均有涉猎）	个人主页
小王同学（算法博客详细，答疑热情，登上热榜第一）	个人主页

Python

小郑（国赛强劲实力选手，热榜常客，求知欲很强）	个人主页
小蓝（算法思路清晰，博客题解详细）	个人主页
秋刀鱼（会三门语言，题解地表最详细）	个人主页

文章很长，因为想让大家真的学会动态规划呀~，而不是只能看到一个斐波那契数列和爬楼梯的例题演示。谢谢观看呀🌹🌹🌹
无限列车意难平，那么准备到无限城中看善逸清理门户叭(柒之型的搜索完成一半啦)

在这里插入图片描述

蓝桥杯国赛十大必备技能——炎之呼吸.叁之型.动态规划

🔔燃烧心灵的炎，照亮动归的光

💓关于动态规划的小阐述

💓壹 - 试题 算法提高 夺宝奇兵

🌱题目描述

🌴解题报告

🌵参考代码(C++版本)

💓贰 - 试题 历届试题 数字三角形【第十一届】【省赛】【C组】

🌱题目描述

🌴解题报告

🌵参考代码(C++版本)

💓叁 - 试题 历届真题 波动数列【第五届】【省赛】【A组】

🌱题目描述

🌴解题报告

🌵参考代码(C++版本)

💓肆 - 试题 历届真题 地宫取宝【第五届】【省赛】【A\B\C组】

🌱题目描述

🌴解题报告

🌵参考代码(C++版本)

💓伍 - 试题 历届真题 调手表【第九届】【决赛】【B组】

🌱题目描述

🌴解题报告

🌵参考代码(C++版本)

💓陆 - 试题 历届真题 砝码称重【第十二届】【省赛】【A/B/C组】

🌱题目描述

🌴解题报告

🌵参考代码(C++版本)

💓柒 - 试题 历届真题 包子凑数【第八届】【省赛】【A/B组】

🌱题目描述

🌴解题报告

🌵参考代码(C++版本)

💓捌 - 试题 历届真题 二进制问题【第十二届】【决赛】【B组】

🌱题目描述

🌴解题报告

🌵参考代码(C++版本)

💓玖 - 试题 历届真题 密码脱落【第七届】【省赛】【A组】

🌱题目描述

🌴解题报告

🌵参考代码(C++版本)

💓拾 - 试题 历届真题 游园安排【第十一届】【决赛】【A/B组】

🌱题目描述

🌴解题报告

🌵参考代码1——dp 70分(C++版本)

🌵参考代码2——贪心 + 二分 100分(C++版本)

💓拾壹 - 试题 历届真题 生命之树【第六届】【省赛】【B组】

🌱题目描述

🌴解题报告

🌵参考代码(C++版本)

💓奥义 - - 第十二届蓝桥杯 C/C++A组 回路计数

🌱题目描述

🌴解题报告

🌵参考代码(C++版本)

💓 总结

💓 关于备战的一点建议

相关问题

公告

DeepSeek全套部署资料免费下载

免费可商用字体批量下载

标签

💓壹 - 试题算法提高夺宝奇兵

💓贰 - 试题历届试题数字三角形【第十一届】【省赛】【C组】

💓叁 - 试题历届真题波动数列【第五届】【省赛】【A组】

💓肆 - 试题历届真题地宫取宝【第五届】【省赛】【A\B\C组】

💓伍 - 试题历届真题调手表【第九届】【决赛】【B组】

💓陆 - 试题历届真题砝码称重【第十二届】【省赛】【A/B/C组】

💓柒 - 试题历届真题包子凑数【第八届】【省赛】【A/B组】

💓捌 - 试题历届真题二进制问题【第十二届】【决赛】【B组】

💓玖 - 试题历届真题密码脱落【第七届】【省赛】【A组】

💓拾 - 试题历届真题游园安排【第十一届】【决赛】【A/B组】

💓拾壹 - 试题历届真题生命之树【第六届】【省赛】【B组】

💓奥义 - - 第十二届蓝桥杯 C/C++A组回路计数