首页 > 其他分享 >动态规划入门指北

动态规划入门指北

时间：2024-10-25 11:12:41浏览次数：5  
标签：指北 10 AC code const 入门 int 动态 dp

P1359 租用游艇

思路

首先设出 \(dp\) 数组：\(dp_i\) 表示走到第 \(i\) 个点时的最小花费。于是乎，建一个反图，对于每一个 \(i\) 找到能与其相连的最小路程。得到转移方程：

\[$ dp_i=min(dp_i,dp_j+mp_{j,i}); $\]

时间复杂度为 \(O(n^2)\)。

AC code

#include<bits/stdc++.h>
using namespace std;
const int N=200;
int dp[N];//dp[i]表示到达i点所需的最少价钱
int n;
int mp[N][N];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n-i;j++){
			int opt;
			cin>>opt;
			mp[i][i+j]=opt;
		}
	}
	for(int i=1;i<=n;i++){
		dp[i]=INT_MAX/2;
	}
	dp[1]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(mp[j][i]!=0&&i!=j){
				dp[i]=min(dp[j]+mp[j][i],dp[i]);
			}
		}
	}
	cout<<dp[n]<<endl;
return 0;
}

P1757 通天之分组背包

思路

分组背包版题。

首先，这个题目与 01 背包不同的是，01 背包是所有的都只能选一个。这个是每个组里只能选一个。对于这样的条件，我们可以对于每一组分别进行 01 背包。

oi-wiki 分组背包讲解

时间复杂度为 \(O(n \times m \times k)\)。

AC code

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int zu[N][N],w[N],v[N];
int cnt[N],mark[N];
int n,m;
int dp[N];
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		cnt[c]++;
		zu[c][cnt[c]]=i;
		w[i]=a;
		v[i]=b;
	}
	memset(dp,1e9,sizeof(dp));
	dp[0]=0;
	for(int k=1;k<N;k++){
		if(cnt[k]){
			for(int i=m;i>=0;i--){
				for(int j=1;j<=cnt[k];j++){
					if(i>=w[zu[k][j]]){
						dp[i]=max(dp[i],dp[i-w[zu[k][j]]]+v[zu[k][j]]);
					}
				}
			}
		}
	}
	cout<<dp[m]<<endl;
return 0;
}

P1832 A+B Problem（再升级）

闲话（乐

人类智慧。

思路

首先，因为只能由质数组成这个数，故先把所有的质数筛出来 （因为数据范围只有1000，故这里我直接采用暴力筛法）。对于每一个质数，可以选无数次。所以可以转换为完全背包。则有 \(dp\) 数组：\(dp_i\) 表示组成 \(i\) 的可能的方案数。得到转移方程：

\[$ dp_j+=dp_{j-i} $\]

其中 \(j\) 表示当前需要组成的数，\(i\) 表示当前所选择的质数。

AC code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10;
int n;
bool check(int x){
	for(int i=2;i<=x-1;i++){
		if(x%i==0){
			return false;
		}
	}
	return true;
}
int dp[N];
bool mark[N]; 	
signed main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		if(check(i)){
			mark[i]=1;
		}
	}
	dp[0]=1;
	for(int i=2;i<=n;i++){
		if(mark[i]==1){
			for(int j=i;j<=n;j++){
				dp[j]+=dp[j-i];
			}
		}
	}
	cout<<dp[n]<<endl;
return 0;
}

P1203 [USACO1.1] 坏掉的项链 Broken Necklace

思路

水

对于每一位预处理出它的左右的红蓝珠子的值即可。最后统计答案的时候对于每一位分别算它左边和右边的红蓝色的最大值相加就可以了。

警钟撅烂（wssb

这题不是对于某一个珠子进行操作，而是对两个珠子的间隙操作捏。。。。。。。。。

AC code

#include<bits/stdc++.h>
using namespace std;
const int N=7e2+10;
int lr[N],lb[N],rr[N],rb[N];
char a[N];
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i+n]=a[i];
	}
	for(int i=1;i<=2*n;i++){
		if(a[i]=='r'){
			lr[i]=lr[i-1]+1;
		}else if(a[i]=='b'){
			lb[i]=lb[i-1]+1;
		}else{
			lr[i]=lr[i-1]+1;
			lb[i]=lb[i-1]+1;
		}
	}
	for(int i=2*n;i>=1;i--){
		if(a[i]=='r'){
			rr[i]=rr[i+1]+1;
		}else if(a[i]=='b'){
			rb[i]=rb[i+1]+1;
		}else{
			rr[i]=rr[i+1]+1;
			rb[i]=rb[i+1]+1;
		}
	}
	int ans=0;
	for(int i=2*n-1;i>=1;i--){
		ans=max(ans,max(lr[i],lb[i])+max(rr[i+1],rb[i+1]));
	}
	cout<<min(ans,n)<<endl;
return 0;
}

P1470 [USACO2.3] 最长前缀 Longest Prefix

思路

首先，分析什么情况下，有目标字符串能被分解。用 \(dp_i\) 表示当前 \(i\) 位之前能否被分解。则 \(dp_i\) 为真的必要条件就是：在 \(i\) 之前有一个 \(j\) 满足 \(dp_j\) 为真，且从 \(j+1\) 到 \(i\) 是一个元素。此时更新答案。

输入有点恶心

AC code

此题就不放代码了 （太丑陋捏

P2858 [USACO06FEB] Treats for the Cows G/S

思路

区间dp板子

首先，以为取数时只能从左右两边取，于是乎，尝试设出 \(dp_{i,j}\) 表示，还剩 \(i\) 到 \(j\) 这个区间的数时已取走的最大价值。然后枚举起点 \(i\) 和终点 \(j\)。则转移方程为：

\[$ dp_{i,j}=max(dp_{i-1,j}+a_{i-1} \times day,dp_{i,j+1}+a_{j+1} \times day) $\]

此处拜谢 tyr_04，注意此处的转移应该注意，是从大范围向小范围转移，故第二重循环因从 \(n\) 到 \(1\)。

AC code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e3+10;
int dp[N][N];
int n;
int a[N];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=n;j>=i;j--){
			int day=n-j+i-1;
			dp[i][j]=max(dp[i-1][j]+a[i-1]*day,dp[i][j+1]+a[j+1]*day);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,dp[i][i]+a[i]*n);
//		cout<<ans<<endl;
	}
	cout<<ans<<endl;
	return 0;
}

P1091 [NOIP2004 提高组] 合唱队形

思路

先将题目中说的最少踢走多少人转换为最多留下来多少人。我们发现，留下来的人就是两个单调不减的序列。故将留下来的人分为两个序列。当枚举的 \(i\) 和 \(j\) 满足上升和下降时，分别有转移方程：

\[$ up_i=max(up_i,up_j+1) $\]

\[$ down_i=max(down_i,down_j+1) $\]

此题结

AC code

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10;
int up[N],down[N],a[N];
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		up[i]=1;
	}
	for(int i=1;i<=n;i++){
		down[i]=1;
	}
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[i]>a[j]){
				up[i]=max(up[i],up[j]+1);
			}
		}
	}
//	for(int i=1;i<=n;i++){
//		cout<<up[i]<<" ";
//	}
//	cout<<endl;
	for(int i=n-1;i>=1;i--){
		for(int j=n;j>i;j--){
			if(a[i]>a[j]){
				down[i]=max(down[i],down[j]+1);
			}
		}
	}
	int ans=1;
	for(int i=1;i<=n;i++){
		ans=max(ans,up[i]+down[i]-1);
	}
	cout<<n-ans<<endl;
return 0;
}

P1077 [NOIP2012 普及组] 摆花

思路

01背包，对于每一种不同的颜色进行背包即可。

时间复杂度：\(O(n*m*a_i)\)。

AC code

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
const int M=1e2+10;
const int mod=1e6+7;
int n,m,tot;
int v[N],a[M];
int dp[N];//dp[i][j]表示当前是第i盆花的，已经放了j盆的方案数
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dp[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=m;j>=1;j--){
			for(int k=1;k<=min(a[i],j);k++){
				dp[j]=(dp[j]+dp[j-k])%mod;
			}
		}
	}
	cout<<dp[m]%mod<<endl;
return 0;
}

P1095 [NOIP2007 普及组] 守望者的逃离

思路

这题可以纯贪心也可以过。大致贪心思路就是：能闪现的时候就闪现，没有闪现且走比闪现要慢的时候，就等闪现。其余时候走。

但是纯贪心着实不好处理。我们尝试用一点 \(dp\) 来处理。先设出 \(dp\) 数组：\(dp_i\) 表示当第 \(i\) 秒的时候，最远走到了哪里。则有转移方程：

当能够闪现的时候：

\[$ dp_i=dp_{i-1}+60 $\]

此时能量值也要变。当不能闪现，但路程大于六十时：

\[$ dp_i=dp_{i-1} $\]

最后在处理一下，走路快的情况，答案即为：\(dp_t\)。

AC code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10;
int m,s,t;
int dp[N];
signed main(){
	cin>>m>>s>>t;
	for(int i=1;i<=t;i++){
		if(m>=10){
			m-=10;
			dp[i]=dp[i-1]+60;
		}else if(m<10){
			m+=4;
			dp[i]=dp[i-1];
		}
	}
	for(int i=1;i<=t;i++){
		dp[i]=max(dp[i],dp[i-1]+17);
		if(dp[i]>=s){
			cout<<"Yes"<<endl;
			cout<<i<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
	cout<<dp[t]<<endl;
return 0;
}

P1435 [IOI2000] 回文字串

思路

首先要想到一点，求最少要加多少个数，就是求总长减去这个字符串与它的反串的最长公共子序列。（这个点很重要，可以通用，经常有类似的题）。于是乎这题就被简化了。有数组 \(dp_{i,j}\) 表示第一个字符串为 \(i\) 位，第二个字符串处于 \(j\) 位时的最大公共子序列。则有：

当 \(s1_i\) 等于 \(s2_j\) 时：

\[$ dp_{i,j}=dp_{i-1,j-1}+1; $\]

当不等时，则有：

\[$ dp_{i,j}=\max(dp_{i-1,j},dp_{i,j-1}) $\]

然后答案就是 \(len - dp_{len,len}\)。

对于最长公共子序列有兴趣的可以看看这个加强版的模板题：P1439 【模板】最长公共子序列。

AC code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10;
int dp[N][N];
char s[N],h[N];
int n;
signed main(){
	cin>>s+1;
	n=strlen(s+1);
//	cout<<n<<endl;
	for(int i=1;i<=n;i++){
		h[n-i+1]=s[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(h[i]==s[j]){
				dp[i][j]=dp[i-1][j-1]+1;
			}else{
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
	}
	cout<<n-dp[n][n]<<endl;
	return 0;
}

P1364 医院设置

思路

呃。。。不知道这个题为什么会放在dp的题单里。思路也很简单：先 floyd 预处理出两个点之间的最短路，然后枚举医院设在哪个位置，计算最小值即可。详见代码。

呃。。。其实 floyd 本质上就是 dp。

AC code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e2+10;
int mp[N][N];
int people[N];
int n;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			mp[i][j]=INT_MAX;
		}
		mp[i][i]=1;
	}
	for(int i=1;i<=n;i++){
		int lson,rson;
		cin>>people[i]>>lson>>rson;
		if(lson){
			mp[i][lson]=1;
			mp[lson][i]=1;
		}
		if(rson){
			mp[i][rson]=1;
			mp[rson][i]=1;
		}
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				mp[i][j]=min(mp[i][k]+mp[k][j],mp[i][j]);
			}
		}
	}
	int ans=INT_MAX;
	for(int i=1;i<=n;i++){
		int opt=0;
		for(int j=1;j<=n;j++){
			if(i!=j){
				opt+=(people[j]*mp[i][j]);
			}
		}
		ans=min(ans,opt);
	}
	cout<<ans<<endl;
	return 0;
}

标签：指北,10,AC,code,const,入门,int,动态,dp
From： https://www.cnblogs.com/OluMel/p/18502086

相关文章

  • C语言基础入门（小白）三种方法解决幽灵换行符问题
    首先，相信很多读者读到题目都会产生一个共同的疑问：什么是幽灵换行符？？？    幽灵换行符是指：在C语言中，当用scanf函数时，想要输入几个字符，比如：当输入‘a’之后按下回车键，运行自动结束，而不是等待输入第二个字符，第二个字符就像幽灵般消失了，这是为什么呢？？    其实，原因......
  • （神经网络和卷积入门）Pytorch小土堆跟练代码（第7天）
    本系列为跟练小土堆每集代码，然后进入李宏毅机器学习教程。在系列中会敲完所有视频中代码，并且在注释详细写出感悟和易错点。欢迎大家一起交流！最前面的软件安装和环境配置部分，可以移步我的另一个帖子一、神经网络'主要在torch.nn里''首先学的是骨架container''Module,所......
  • 电赛入门之硬件基本电路
    刚上手可以跟着一起做一些小的电路模块，逐步了解各个名词。初学阶段可以不用掌握电路的设计计算，会抄就行，其实抄的多了之后自然就会了。硬件的电路基础框架来来回回就是那些电路的拼接一、放大电路放大电路的物理原理就是初中学的分压电路，更简单来说倍数就是一个比值。而由于......
  • 电赛入门之硬件焊接
    焊接是每个电赛选手必备的功底，电赛四天三夜时间紧任务重，一遍焊成率一定是非常重要的技能。毕竟你也不想因为虚焊和失误导致查板子查一晚上吧（泪）。在学习过程中你肯定会查出来自己各种各样哭笑不得的错误，比如说芯片引脚忘焊，二极管焊反，不小心把信号线接了地、电源线断了.....不......
  • 【粉丝福利社】R语言统计分析与可视化从入门到精通
    标题详情作者简介愚公搬代码头衔华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，CSDN商业化专家，阿里云专家博主，阿里云签约作者，腾讯云优秀博主，腾讯云内容共创官，掘金优秀博主，亚马逊技领云博主，51CTO博客专家等。近期荣誉2022年度博客之星TOP2，2023年度......
  • JS-基础入门
    JavaScript入门JavaScript是解释性的弱类型编程语言解释性:逐行解释,逐行执行弱类型:不区分变量的数据类型JS的组成一般认为浏览器中JavaScript由三部分组成ECMAScript:基础语法由ECMA（原欧洲计算机制造商协会）进行标准化的一门编程语言,主要规定了像变量,数据类型,......
  • 零基础C语言入门第四课——分支（上）
    文章目录开篇一、if语句1.1if1.2else1.3分支中包含多条语句1.4嵌套if开篇本篇文章还没写完，后面会继续修改编辑，把分支的笔记整合到一起，大家可以先收藏，后面就可以看到完整版的笔记了前面我们说过，C语言是结构化的程序设计语言，这里的结构指的是顺序结构、选择结构、......
  • CPP vector动态数组的基本用法
    #include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intmain()#defineintlonglong//不能放在主函数之前，因为主函数的返回类型必须是int{ vector<int>v={0,0,0,0}; v.push_back(1); v.push_back(2); v.push_back(2); v.push_back(3......
  • 面试华为遇到了经典动态规划题 - 怎么用go、C++进行编程解决
    华为的知名很大程度上源自于在经历过被美国的制裁和打压后不仅撑住了，而且还做出了相对于自己来说技术进步程度很大的芯片​。这是一个不小的成绩​。从个人的角度上来说，华为是最难进的一家大公司之一，它的面试标准很严格​。这不仅是筛选人才，在某种程度上来说也是由于求职市场......
  • 英飞凌AURIX SafeTpack配置入门
       1024程序员节日快乐！！！Hitex按照ISO26262标准作为安全要素开发，系统需要根据不同ASIL等级的要求，针对不同比例的单点故障（SPF）和潜在故障（LF）进行检测，为英飞凌AURIX系列芯片的功能安全提供解决方案。文章按照Hitex提供的基于EBTresos工具用于模块自定义配置SafeTpack开发的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99