Peter算法小课堂—动态规划

2024-02-25 18:04
文章标签 算法 动态 规划 课堂 peter

本文主要是介绍Peter算法小课堂—动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Peter来啦，好久没有更新了呢

今天，我们来讨论讨论提高组的动态规划。

动态规划

动态规划有好多经典的题，有什么背包问题、正整数拆分、杨辉三角……但是，如果考到陌生的题，怎么办呢？比如说2000年提高组的乘积最大、石子合并……，所以说，我们要理解动态规划的本质。

那么，我们动态规划的第一步就是状态定义

dp的第二步就是填表格、写状态转移方程。

最后一步就是根据状态转移方程写代码了。其实，我觉得，dp最难的地方就是第二步，其次就是根据递推式写代码。给大家练一练根据递推式写代码吧。

递推1

那么，代码很简单，长这样👇

#include<bits/stdc++.h>
using namespace std;
int f[110][1010],n,v,c[110],w[110];
int main()
{scanf("%d%d",&v,&n);for (int i=1;i<=n;++i)scanf("%d%d",&c[i],&w[i]);for (int i=1;i<=n;++i) {for (int j=1;j<c[i];++j)f[i][j]=f[i-1][j];for (int j=c[i];j<=v;++j)f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);}printf("%d\n",f[n][v]);return 0;
}

再来一道题

递推2

代码长这样

#include<bits/stdc++.h>
using namespace std;
int f[1010],n,c[1010];
int main()
{scanf("%d",&n);for (int i=1;i<=n;++i)scanf("%d",&c[i]);for (int i=1;i<=n;++i)for (int j=1;j<=i;++j)f[i]=max(f[i],f[i-j]+c[j]);int k,x;scanf("%d",&k);for (int i=1;i<=k;++i) {scanf("%d",&x);printf("%d\n",f[x]);}return 0;
}

递推练完了，就要练习状态转移方程了（靠自觉）

摆花

原题链接：P1077 [NOIP2012 普及组] 摆花 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

那么这道题，我们把题意抽象化成：有 n 个数（c1​,c2​,...,cn​），0⩽ci​⩽ai​,求有多少种方案数使\sum_{i=1}^{n}c_{i}=m。

首先，看到这道题，我给出5种办法，分别对应初学者、普及Oler、不大聪明的提高Oler、灰常聪明的提高Oler。

初学者

最最最简单的办法就是搜索+记忆化

#include<bits/stdc++.h>
using namespace std;
const int maxn=105, mod = 1000007;
int n, m, a[maxn], rmb[maxn][maxn];
int dfs(int x,int k)
{if(k > m) return 0;if(k == m) return 1;if(x == n+1) return 0;if(rmb[x][k]) return rmb[x][k]; //搜过了就返回int ans = 0;for(int i=0; i<=a[x]; i++) ans = (ans + dfs(x+1, k+i))%mod;rmb[x][k] = ans; //记录当前状态的结果return ans;
}
int main()
{cin>>n>>m;for(int i=1; i<=n; i++) cin>>a[i];cout<<dfs(1,0)<<endl;return 0;
}

搜索所有可能的c_{i}并且记忆化。

普及Oler

其次，应该会想到动态规划了。

时间复杂度大大降低，给出代码

#include <bits/stdc++.h>
using namespace std;
const int N=109;
const int MOD=1e6+7;
int f[N][N],a[N],n,m;
int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];f[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){if(j-1<a[i])f[i][j]=(f[i-1][j]%MOD+f[i][j-1]%MOD)%MOD;else f[i][j]=(f[i-1][j]%MOD+f[i][j-1]%MOD-f[i-1][j-1-a[i]]%MOD+MOD)%MOD;}}cout<<f[n][m]<<endl;return 0;
}

还是比较蒟蒻的

不大聪明的提高Oler

再其次，就是前缀和优化，大家都学过，给出代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105, mod = 1000007;
int n, m, f[maxn], sum[maxn], a[maxn];
int main(){cin>>n>>m;for(int i=1; i<=n; i++) cin>>a[i];f[0] = 1;for(int i=0; i<=m; i++) sum[i] = 1;for(int i=1; i<=n; i++){for(int j=m; j>=1; j--){int t = j - min(a[i], j) - 1;if(t < 0) f[j] = (f[j] + sum[j-1])%mod;else f[j] = (f[j] + sum[j-1] - sum[t] + mod)%mod;}for(int j=1; j<=m; j++) sum[j] = (sum[j-1] + f[j])%mod;}cout<<f[m]<<endl;return 0;
}

来了，它又来了，它就是我们的生成函数！！！

灰常聪明的提高Oler

生成函数啊啊啊

大家如果不会生成函数的话，可以康康这位大佬的博客生成函数(母函数)——目前最全的讲解-CSDN博客

我们构造一个函数g(x)=\prod_{i=1}^{n}\sum_{j=0}^{a_{i}}x^{j}，其中x^{m}项的系数即为答案。可以做n-1次NTT，然后输出。时间复杂度：O(n^2k\log nk)。这里我不给出代码了。

其实，也不用算出乘积，有一种更好的方法

我们约定A(x)=\sum_{i=0}^{n}a_{i}x^{i}，B(x)=\sum_{i=0}^{n}b_{i}x^{i}，

若C(x)=A(x)B(x)， 则C(x)=\sum_{i=0}^{n+m}c_{i}x^{i}，其中c_{i}=\sum_{j=0}^{i}a_{j}b_{i-j}，懂得都懂

这一题比较难，来一道简单亿点的题

参差不齐

n名电影演员依次排成一排，第i人的颜值为y[i]，有些参差不齐。你希望挑选m个人拍一张电影海报，这m个人的前后顺序不能发生变化。你希望挑选的这排演员相邻的颜值不能相差太大，于是你定义颜值的参差不齐程度为相邻两人颜值差距的绝对值之和。求这m人的参差不齐程度最少是多少？

这一题最难的是状态定义，要是状态定义完成了的话，状态转移方程就显而易见了。

这个定义不太好，下面给出正确的定义及代码

下面给出代码👇

for(int i=1;i<=n;i++) f[i][1]=0;
for(int j=2;j<=m;j++)//枚举j代表选中人数for(int i=j;i<=n;i++){//枚举i代表结尾编号f[i][j]=INF;for(int k=j-1;k<i;k++)//结尾是i号时枚举k代表i号的左边邻居是几号f[i][j]=min(f[i][j],f[k][j-1]+abs(y[i]-y[k]));}
int ans=INF;
for(int i=m;i<=n;i++) ans=min(ans,f[i][m]);
cout<<ans<<endl;

乘积最大

原题链接：P1018 [NOIP2000 提高组] 乘积最大 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这题显然是一道数位dp

状态定义：f[i][j] 表示前 i 位数包含 j 个乘号所能达到的最大乘积

easy代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long f[45][60];
string in;
int n,k;//n位数  k个乘号 
long long g[45];
long long cut(int l,int r){long long end = 0;for(int i = l;i <= r;i++)end = end * 10 + g[i];return end;
}
int main(){cin >> n >> k >> in;for(int i = 1;i <= n;i++)g[i] = in[i - 1] - '0';for(int i=1;i<=n;i++)f[i][0] = cut(1,i);for(int i = 2;i <= n;i++){ //枚举分割为前i位数字 for(int a = 1;a <= min(i-1,k);a++){ //枚举有几个乘号 for(int b = a;b < i;b++){ //在第几位放乘号 f[i][a] = max(f[i][a],f[b][a-1] * cut(b + 1,i));}}}cout<<f[n][k];return 0;
}

然后，就是我们的毒瘤最后一题啦

面条切割

这一题涉及到动态规划的本质，但是这一题要用到微积分，所以……

原题链接：Problem - 5984 (hdu.edu.cn)

设长度为x的面条期望为f(x)。显然，当x<d时，f(x)=0。当x>b时，设t为0~x上的坐标值，吃掉t~x上的面条，剩下的面条就是0~t，即吃掉剩下的面条次数期望为f(t) 。dt为一个很小的线元，点落在dt上的概率为\frac{dt}{x}，而dt贡献的期望为：dt的长度为t，如上所述，贡献了f(t)的期望。最后我们再把这些相加（积分），得到f(x)=1+\frac{\int_{d}^{x} f(t)dt}{x}。接下来就是解出f(x)了。我们可以对f(x)求个导，然后还原，如下（LateX难打）

于是乎，f(x)=\ln x+C。然后，我们代一个特指进去，随便哪一个都行，最好是x=d，然后得到C=1-\ln d。综上所述，f(x)=\ln \frac{d}{x}+1。代码来啦

#include <bits/stdc++.h>
using namespace std;
int main() {int T;cin >> T;while (T--) {double a, b;cin >> a >> b;if (a <= b)cout << "0.000000" << endl;elsecout << fixed << setprecision(6) << 1.0 + log(a / b) << endl;}return 0;
}

时间复杂度几乎为O(1)！

OK！今天就讲到这里，886

这篇关于Peter算法小课堂—动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/746266。

相关文章

C#如何动态创建Label,及动态label事件

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》：本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点：switch中的生成我们的label事件接着，
阅读更多...
SpringCloud动态配置注解@RefreshScope与@Component的深度解析

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.
阅读更多...
MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL？1.2 动态SQL的优点1.3 动态S
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
mybatis-plus 实现查询表名动态修改的示例代码

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...
基于Canvas的Html5多时区动态时钟实战代码

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》：本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示，通过Canvas的API，可以绘制出6个不同城市的时钟，并且这些时钟可以动态转动，每个时钟上都会标注出对应的24小时制时间，详细内容请阅读本文，希望能对你有所帮助...
阅读更多...
Vue中动态权限到按钮的完整实现方案详解

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表（routes）1.2 修改角色与路由权限表（role_routes）二、后端接口设计
阅读更多...
前端 CSS 动态设置样式：:class、:style 等技巧(推荐)

前端 CSS 动态设置样式：:class、:style 等技巧(推荐)

《前端CSS动态设置样式：:class、:style等技巧(推荐)》：本文主要介绍了Vue.js中动态绑定类名和内联样式的两种方法：对象语法和数组语法，通过对象语法，可以根据条件动态切换类名或样式；通过数组语法，可以同时绑定多个类名或样式，此外，还可以结合计算属性来生成复杂的类名或样式对象，详细内容请阅读本文，希望能对你有所帮助...
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2