蓝桥杯十大常见天阶功法——炎之呼吸.叁之型.动态规划--(上篇)

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

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

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

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

🌱题目描述

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

🌴解题报告

注意最大数目看到这个潜意识想是不是要找最优解了?最优解？？动态规划治的就是最优解

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

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

对这个类处理的时候因为它们最后都肯定会走到(4,2)这个点。

这里就又出现了一个之后文章会反复提起的一句话把全班分数整体减10分第一名还是第一名整体情况不受到影响但是更加利于数据分析

同样我们先将(4,2)剔除就可以很清晰处理最后一个不同点——是从左上转移过来还是右上转移过的。处理好了补加上这个必定经过的点

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

#include <iostream>
#include <cstdio>
#include <algorithm>

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组】

线性动归规划——数字三角形的进阶+掌握数论小知识

🌱题目描述

原题传送门

🌴解题报告

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

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

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

一个小小的脑筋急转弯

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

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

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

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

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

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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

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];
	
	//开始DP
	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 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;
}

💓叁 - 历届真题 蓝肽子序列【第十一届】【决赛】【研究生组】

线性动态规划中的最长公共子序列模型 + 最大值这个属性是可以重复的

🌱题目描述

原题传送门

🌴解题报告

公共子序列的题大多数是可以很明显的看到公共、公共长度等字眼

因为数据范围是1000嘛可能有小伙伴想的暴力一下？因为在公共子序列匹配的时候当前这个位置可以相同也可以不相同那么就是$2^{1000}$次的运算所以只能转而求其次使用可以优化暴力的动态规划。

最长公共子序列的常规模型的分析方式

最长公共子序列的常规分析方式还是有点小小的模板的味道顺着闫式DP分析的思路系统的演示一下怎么获得状态转移方程~

假如有两个子序列分别叫做$a$和$b$

状态表示

集合f[i][j]表示a的前i个字母和b的前j个字母的最长公共子序列长度的集合

属性最大值

状态计算

状态计算对应的是集合划分的过程划分的依据是当前能利用起来的最后一个不同点。

这里有个划分细节是以前在y总的课中听到的可以注意心中有个底就好现阶段不必纠结的有个印象能Ac比啥都好。

好了清楚了这个以后就可以着手落实代码啦~

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

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;

int f[N][N];
string s1, s2;
string str1[N], str2[N];
int cnt1, cnt2;

int main()
{
	//输入
    cin >> s1 >> s2;
    
    //获取两个字符串长度
    int len1 = s1.length(), len2 = s2.length();
    
	//分割蓝肽
    for (int i = 0; i < len1;)
    {
        //遇到大写字母就是遇到蓝肽了
        if (s1[i] >= 'A' && s1[i] <= 'Z')
        {
            str1[++cnt1] += s1[i++];
            while (s1[i] >= 'a' && s1[i] <= 'z') str1[cnt1] += s1[i++];
        }
    }
    
    for (int i = 0; i < len2;)
    {
        if (s2[i] >= 'A' && s2[i] <= 'Z')
        {
            str2[++cnt2] += s2[i++];
            while (s2[i] >= 'a' && s2[i] <= 'z') str2[cnt2] += s2[i++];
        }
    }
    
    
    for (int i = 1; i <= cnt1; i++)
        for (int j = 1; j <= cnt2; j++)
        {
            if (str1[i] == str2[j]) f[i][j] = f[i - 1][j - 1] + 1;
            else f[i][j] = max(f[i][j - 1], f[i - 1][j]);
        }
        
    cout << f[cnt1][cnt2] << endl;
    
    return 0;
}

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

选择模型中的01背包的变型

🌱题目描述

原题传送门

🌴解题报告

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

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

系统温习背包问题

背包问题中$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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
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;
	return 0;
}

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

选择模型中的完全背包+掌握数论互质判断(gcd)

🌱题目描述

原题传送门

🌴解题报告

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

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

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

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

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

当两个整数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个就可以凑出jf[i-1,j k * v[i]]

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

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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

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]);
	
	//判断最大公约数是否大于1
	if(x > 1) printf("INF\n");
	
	//最大公约数为1也就说它们是互质的那么开始DP
	else
	{
		//初始化
		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分析图会不会有小伙伴潜意识中逐渐以为做动态规划一定要画闫式DP分析图了？我当初就是这种的想的太呆萌了😭😭😭

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

🌴解题报告

一、意识培养

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

二、温习完全背包

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

三、降服本题

这道题中+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 <iostream>
#include <algorithm>
#include <cstdio>

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

💓 关于动态规划的一点建议

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

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

💓 比赛将至咱不懂就问~

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

C/C++

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

Java

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

Python

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

到这儿了动态规划中比较简单的内容算是告一段落解决完上一要着手迎战三哥了