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

这篇具有很好参考价值的文章主要介绍了蓝桥杯十大常见天阶功法——炎之呼吸.叁之型.动态规划--(上篇)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

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

因为自己太贪心了叭,想把动态规划怎么思考、怎么分析、常见模型都总结清楚,导致叁之型第一次发(周一发的)的时候,特别的冗长,所以自己再次整改了一下内容,可能真的特别长吧,csdn的编辑器写着写着都崩十几回...

上篇对应动漫中的迎战下弦一魇梦,整体比较和谐轻松的

下篇对应动漫中的决战上弦三猗窝座,整体节奏相对比较难啃。两篇配合起来,适合B组的大部分小伙伴以及A组的部分小伙伴吧~


往期精彩

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

💓叁之型上篇总览

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

💓动态规划简述

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

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题


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


系统的提一下思考方向是很多滴,选一种顺手的~
不管黑猫白猫了,只要能Ac的,都是好喵喵~

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

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

听闫总讲课说,动态规划可以理解为对暴力的优化

因为暴力是逐个逐个的处理每种情况,可想而知,其中存在大量的重复情况。动态规划就是将一些相似的情况化零为整了。

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

acwing师兄总结了这张DP分析图十分全面,感谢师兄🌹🌹🌹

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

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

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

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

线性动态规划模型——经典的"数字三角形"的翻版,因为状态转移过程十分清晰,十分适合作为入门之选。

🌱题目描述

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

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

🌴解题报告

注意最大数目,看到这个,潜意识想是不是要找最优解了?最优解??,动态规划治的就是最优解!
炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

记住这个一种线性DP的模型。它的背景是数字三角形,可能是大多数学动态规划的小伙伴的启蒙题目了吧。
炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

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

动态规划的本质了,说直白一点,不整高大上的概念,有点类似于一个递推的过程。

那么我们在划分状态的时候可以将,得到当前状态最后一个不同点作为划分的依据。

因为是递推,下一个状态的时候,也是如此与考虑,那么整个过程就自底向上的将问题逐渐解决了。

闫式DP分析法:

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

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


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

将上述文字做成一张图,就是一张这种效果的闫式DP分析图:
炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

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

因为,首先我们整体是一个归类的思想,所有从顶点走到图示中(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组】

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

🌱题目描述

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

原题传送门

🌴解题报告

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

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

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

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

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

一个小小的脑筋急转弯


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

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

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

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

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

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

🌵参考代码(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;
}

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

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

🌱题目描述

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

原题传送门

🌴解题报告

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

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

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

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

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

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

状态表示:

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

属性:最大值

状态计算:

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

这里有个划分细节,是以前在y总的课中听到的,可以注意,心中有个底就好,现阶段不必纠结的,有个印象,能Ac比啥都好。
炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

对于本题而言:可以依据a[i]和b[j]是否包含在当前的子序列中来划分。

情况一a[i] 和 b[j]都不在此时状态转移方程为f[i-1][j-1]

情况二a[i]不在,b[j]在此时状态转移方程可以写为:f[i-1][j]

这里了,看似是f[i−1][j] ,实际上无法用f[i−1][j]表示的。

因为f[i−1][j]表示的是在 a a a的前 i − 1 i-1 i1个字母中出现,并且在 b b b的前 j j j个字母中出现,此时b[j]不一定出现,这与条件不完全相等。
当前情况是a[i]一定不在子序列中,b[j]一定在子序列当中。
但仍可以用f[i−1][j]来表示,因为是当前情况是f[i-1][j]的一个子集,咱们要求的是max,不影响结果。

这就是我上文说的,在划分的时候,本来是要严格遵守不重不漏的原则,但是对于最大值而言,是可以重复的。

情况三a[i]在,b[j]不在此时状态转移方程可以写为:f[i][j-1]

情况四a[i]和b[j]都在此时状态转移方程为f[i-1][j-1] + 1


综上所述,可以得到这闫式DP分析图。
炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

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

🌵参考代码(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背包的变型

🌱题目描述

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

原题传送门

🌴解题报告

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

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

系统温习背包问题:

背包问题中 f [ i ] [ j ] f[i][j] f[i][j]表示从前 i i i个物品中进行选择,在背包容量为 j j 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分析图
炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题
同样的,对应一定会选择的砝码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)

🌱题目描述

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

原题传送门

🌴解题报告

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

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

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

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

对于常规情况下,完全背包状态转移方程通式的获得是经过如下的闫式分析以及数学归纳之后的结果,我只是放置在这儿,不去证明了。

根据小伙伴们的需求,能理解性的记忆最好。假如时间吃紧的话也可以直接背下来先用着,以后再回头理解它的时候回会很轻松的.

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

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

当两个整数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 <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分析图了?我当初就是这种的想的,太呆萌了😭😭😭
炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

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


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

举个不好听的例子吧,很多博客讲动态规划都是斐波那契数列跳台阶。我是真的不知道这两个直接可以三分钟内想出转移方程的题为什么要被这么多博主反复赘述,可能因为比较经典…

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题


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

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

🌱题目描述

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题
原题传送门1
原题传送门2

🌴解题报告

一、意识培养

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

二、温习完全背包

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

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题


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

状态表示:

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

状态计算:

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

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

小伙们也可以看这张出上述步骤总结出来的闫式DP分析图,稍显凌乱了
炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

三、降服本题

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

闫式DP分析

状态表示:

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

这个题有点逗,它问题的意思是让咱们求一批最小调整方案中的最大值…离谱
炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题

状态计算:

要么从+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分析的帮助下,再去试着刷,然后就会感觉看到一些题就知道,可以用动态规划,甚至可以有直接秒出状态转移方程的感觉的,大家要相信自己呀。

💓 比赛将至,咱,不懂就问~

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

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题
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😊

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

炎之呼吸三之行,约战蓝桥,各自努力,顶峰相见,算法,动态规划,LCS,背包问题文章来源地址https://www.toymoban.com/news/detail-794416.html

到了这里,关于蓝桥杯十大常见天阶功法——炎之呼吸.叁之型.动态规划--(上篇)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 堆排序——我欲修仙(功法篇)

    个人主页:【😊个人主页】 系列专栏:【❤️我欲修仙】 学习名言:学习和研究好比爬梯子,要一步一步地往上爬,企图一脚跨上四五步,平地登天,那就必须会摔跤了。——华罗庚 第一章 ❤️ 学习前的必知知识 第二章 ❤️ 二分查找 在数据结构与算法的世界里,有六种

    2024年02月05日
    浏览(26)
  • 产品经理功法修炼(4)之产品管理

    点击下载《产品经理功法修炼(4)之产品管理》 产品经理功法修炼(1)之自我管理 产品经理功法修炼(2)之专业技能 产品经理功法修炼(3)之产品设计 产品经理功法修炼(4)之产品管理 产品经理功法修炼(5)之团队管理 产品经理的能力修炼并非局限于某一技能的速成

    2024年04月09日
    浏览(85)
  • 怎么提升数据分析能力?——功法篇(下)

    先来复习一下上篇提到的3个疑问: 为什么我做出来的分析总觉得没有别人的那么高级? 老板为什么总说我的分析“太浅了”? 数据分析师每天的工作就是取数做需求? 看完上篇讲的金字塔原理,如果你还有疑问,不妨再认识一下另一个数据分析的无上功法: 自从某一次马

    2024年01月23日
    浏览(39)
  • 三大基础排序算法——我欲修仙(功法篇)

    个人主页:【😊个人主页】 系列专栏:【❤️我欲修仙】 学习名言:莫等闲、白了少年头,空悲切。——岳飞 第一章 ❤️ 学习前的必知知识 第二章 ❤️ 二分查找 所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。排序算法

    2024年02月07日
    浏览(25)
  • 【蓝桥杯备赛Java组】语言基础|竞赛常用库函数|输入输出|String的使用|常见的数学方法|大小写转换

    🎥 个人主页:深鱼~ 🔥收录专栏:蓝桥杯 🌄欢迎 👍点赞✍评论⭐收藏 目录 一、编程基础 1.1 Java类的创建  1.2 Java方法  1.3 输入输出  1.4 String的使用 二、竞赛常用库函数 1.常见的数学方法 2.大小写转换 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,

    2024年01月21日
    浏览(75)
  • 【蓝桥杯备赛Java组】第一章·语言基础|竞赛常用库函数|输入输出|String的使用|常见的数学方法|大小写转换

    🎥 个人主页:深鱼~ 🔥收录专栏:蓝桥杯 🌄欢迎 👍点赞✍评论⭐收藏 目录 一、编程基础 1.1 Java类的创建  1.2 Java方法  1.3 输入输出  1.4 String的使用 二、竞赛常用库函数 1.常见的数学方法 2.大小写转换 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,

    2024年01月19日
    浏览(79)
  • HOJ 系统常用功能介绍 OJ部署定制快速入门 c++ python Java编程在线自动评测判题 信息奥赛一本通 USACO G E S P 蓝桥 CSP NOIP 蓝桥等考题库 常见问题

    技术支持微  makytony   终身更新维护 功能类似洛谷和信息奥赛一本通,支持CSP复赛中的freopen文件输入输出方式提交,模拟真实考试环境,防止出现 本地  AC 比赛  WA  PA TLE  爆零 的惨剧。 组织比赛作业,创建题目、查看用户提交代码、下载评测数据等都没限制。 约  328

    2024年01月25日
    浏览(37)
  • LabVIEW开发呼吸分析系统

    LabVIEW开发呼吸分析系统 在日常生活中,许多人都在练习调息法,但大多数人都不知道如何以完美的方式做。不当的做法不会带来适当的结果。一种使用LabVIEW分析呼吸信号的方法,以使人们以完美的方式练习调息。这有助于从业者按照系统指定的说明来控制他们的呼吸。 该系

    2024年02月09日
    浏览(47)
  • PWM 呼吸灯实验

    FPGA实现一个PWM模块(硬件)来控制灯的亮灭。 PWM本质上就是一个输出脉冲的硬件,通过改变一个周期高电平(占空比)的时间来对其他的硬件进行控制,比如电机。 呼吸灯的实现利用了人眼的视觉特性,控制灯亮和暗的间隔时间就形成了对灯亮度的调节。 通过一个N比特的

    2023年04月27日
    浏览(37)
  • 呼吸灯——FPGA

    环境: 1、Quartus18.0 2、vscode 3、板子型号:EP4CE6F17C8 要求: 将四个LED灯实现循环从亮到灭、灭到亮的过程。下面我使用了两种方法供大家阅读。 呼吸灯其实是在微处理器的控制下,由暗渐亮、然后再由亮渐暗,模仿人呼吸方式的 LED 灯。 呼吸灯采用 PWM 的方式,在固定的频率

    2024年02月16日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包