首页 > 其他分享 >动态规划做题笔记

动态规划做题笔记

时间：2024-02-03 11:56:11浏览次数：26  
标签：underset le 子段 int max 笔记 序列 动态 规划

目录

线性动态规划

[NOIP1999 提高组] 导弹拦截

第一问求最长不上升子序列，第二问可以考虑贪心，从左到右依次枚举每个导弹。假设现在有若干个导弹拦截系统可以拦截它，那么我们肯定选择这些系统当中位置最低的那一个。如果不存在任何一个导弹拦截系统可以拦截它，那我们只能新加一个系统了，这个过程等价于求最长上升子序列。

\(O(n^2)\) 的算法如下：

状态：\(f_{i}\) 表示以 \(a_i\) 结尾的最长上升子序列的长度。

阶段：子序列的结尾在原序列中的位置。

转移：\(f_{i}= \underset{0 \le j < i,a_{i} < a_{j}}{\max}\{f_{j}+1\}\)。

边界：\(f_{0}=0\)

目标：\(\underset{1 \le i \le n}{max}\)

求最长不下降子序列的方法与之类似。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[100005],t,n,f[100005],ans;
int main(){
	while(cin>>t){
		a[++n]=t;
		f[n]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<i;j++){
			if(a[j]>=a[i]){
				f[i]=max(f[i],f[j]+1);
			}
		}
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,f[i]);
	}
	cout<<ans<<endl;
	ans=0;
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++){
		for(int j=0;j<i;j++){
			if(a[i]>a[j]){
				f[i]=max(f[i],f[j]+1);
			}
		}
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,f[i]);
	}
	cout<<ans;
	return 0;
}

这个算法可以通过原数据，但是对于本题来说，我们需要使用 \(O(n \log n)\) 的算法。我们可以考虑用二分优化 DP。

定义 \(f_{i}\) 表示对于所有长度为 \(i\) 的单调不上升子序列，它的最后一项最大值。随着 \(i\) 的增大，\(f\) 一定单调不上升。

记 \(f\) 的长度为 \(len\)。对于每一个 \(a_{i}\)，分两种情况讨论：

  1. 若 \(a_{i} \le f_{len}\)，则将 \(a_{i}\) 从 \(f\) 的末尾加入。

  2. 若 \(a_{i} > f_{len}\)，则在 \(f\) 中二分查找第一个小于 \(a_{i}\) 的数并用 \(a_{i}\) 替换它。

为什么可以这么处理第二种情况呢？这是因为若以一个较小的数作为不上升子序列的结尾，则在接下来的尝试中，这个子序列“下降”的空间较小。若以一个较大的数作为不上升子序列的结尾，则在接下来的尝试中，这个子序列“下降”的空间较大。

求最长上升子序列的优化方法与之类似。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[100005],t,n,f[100005],ans;
int main(){
	while(cin>>t){
		a[++n]=t;
	}
	f[1]=a[1];
	ans++;
	for(int i=2;i<=n;i++){
		if(f[ans]>=a[i]) f[++ans]=a[i];
		else f[upper_bound(f+1,f+1+ans,a[i],greater<int>())-f]=a[i];
	}
	cout<<ans<<endl;
	memset(f,0,sizeof(f));
	ans=0;
	f[1]=a[1];
	ans++;
	for(int i=2;i<=n;i++){
		if(f[ans]<a[i]) f[++ans]=a[i];
		else f[lower_bound(f+1,f+1+ans,a[i])-f]=a[i];
	}
	cout<<ans;
	return 0;
}

尼克的任务

直觉告诉我们，可以定义 \(f_{i}\) 表示到从第 \(1\) 分钟到第 \(i\) 分钟
的最大空闲时间，经过尝试后发现很难推出状态转移方程，于是正难则反，定义 \(f_{i}\) 表示第 \(i\) 分钟到第 \(n\) 分钟的最大空闲时间，采用逆序遍历的方式。

状态：\(f_{x}\) 表示从第 \(x\) 分钟到第 \(n\) 分钟的最大空闲时间。

阶段：第 \(x\) 分钟。

转移：\(f_x = \begin{cases} f_{x+1} + 1 & \text{无任务开始} \\ \underset{1 \le i \le y}{\max}\{f_{x+a_i}\} & \text{当前有 y 个任务开始，第 i 个任务的结束时间为 a_i} \\ \end{cases}\)

边界：\(f_{n}=0\)。

目标：\(f_{1}\)

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,k,f[10005];
vector<int> v[10005];
int main(){
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		int t1,t2;
		cin>>t1>>t2;
		v[t1].push_back(t2);
	}
	for(int i=n;i>=1;i--){
		if(v[i].size()==0){
			f[i]=f[i+1]+1;
			continue;
		}
		for(int j=0;j<v[i].size();j++){
			f[i]=max(f[i],f[i+v[i][j]]);
		}
	}
	cout<<f[1];
	return 0;
}

双子序列最大和

我们先来考虑如何求一个序列的最大子段和。

状态：\(f_i\) 表示以在原序列中的第 \(i\) 个位置结尾的最大子段和。

转移：\(f_i=\max(f_{i-1},a_i)\)。

边界：\(f_1=a_1\)。

目标：\(f_n\)。

当然也可以使用线段树来解决这个问题，这里不赘述。

那么如何求解本题呢？

由于选出的两个子段必须至少间隔一个位置，所以我们可以考虑间隔的一个位置 \(i\)，那么答案就是第 \(i\) 个位置前的最大子段和与第 \(i\) 个位置后的最大子段和，并且两段子段不相交，满足题意。

状态：\(f_{i}\) 表示在原序列中以 \(i\) 结尾的最大子段和，\(g_{i}\) 表示在原序列中以 \(i\) 开头的最大子段和。

转移:\(f_{i}=\max(f_{i-1},a_{i}),g_{i}=\max(g_{i+1},a_{i})\)。

目标：记 \(x_{i}=\underset{1 \le j \le i}{max}\{f_{j}\},y_{i}=\underset{1 \le j \le i}{max}\{g_{j}\}\)，目标即为 \(\underset{2 \le i \le n-1}{max}\{x_{i-1}+y_{i+1}\}\)。

边界：\(f_{1}=a_{1},g_{n}=a_{n}\)。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],f1[1000005],f2[1000005],ans=-(1<<30);
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	f1[1]=a[1];
	f2[n]=a[n];
	for(int i=2;i<=n;i++) f1[i]=max(f1[i-1]+a[i],a[i]);
	for(int i=2;i<=n;i++) f1[i]=max(f1[i-1],f1[i]);//这里求的就是目标中的x[i]，表示的不是以i结尾的最大子段和，而是1~i的最大子段和
	for(int i=n-1;i>=1;i--) f2[i]=max(f2[i+1]+a[i],a[i]);
	for(int i=n-1;i>=1;i--) f2[i]=max(f2[i+1],f2[i]);//这里求得就是目标中的y[i]，表示的不是以i开头的最大子段和，而是i~n的最大子段和
	for(int i=2;i<n;i++) ans=max(ans,f1[i-1]+f2[i+1]);
	cout<<ans;
	return 0;
}

Flowers

本题的实质就是给最长上升子序列加了一个权值。

状态：\(f_i\) 表示以在原序列中的第 \(i\) 个位置结尾的满足条件的最大答案。

转移：\(f_{i}= \underset{0 \le j < i,a_{i} < a_{j}}{\max}\{f_{j}|h_{j} < h_{i}\}+a_i\)。

目标：\(\underset{1\le i \le n}{\max}\{f_i\}\)。

边界：\(f_i=a_i(1\le i \le n)\)。

时间复杂度为 \(O(n^2)\)，本题的数据范围为 $ 1\ \leq\ N\ \leq\ 2\ ×\ 10^5 $，无法承受。

在状态转移方程中，求满足条件的最大的 \(f_{j}\) 的操作可以使用线段树优化。

优化后的时间复杂度为 \(O(n \log n)\)，可以通过本题。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,h[200005],a[200005];
long long f[200005],ans=-(1<<30);
struct node{
	int l,r;
	long long dat;
	#define l(x) t[x].l
	#define r(x) t[x].r
	#define dat(x) t[x].dat
}t[200005*4];
void build(int p,int l,int r){
	l(p)=l;
	r(p)=r;
	if(l==r){
		dat(p)=0;
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	dat(p)=0;
}
void change(int p,int x,long long v){
	if(l(p)==r(p)){
		dat(p)=v;
		return;
	}
	int mid=(l(p)+r(p))>>1;
	
	if(x<=mid) change(p<<1,x,v);
	else change(p<<1|1,x,v);
	dat(p)=max(dat(p<<1),dat(p<<1|1));
}
long long ask(int l,int r,int p){
	if(l<=l(p) && r>=r(p)) return dat(p);
	int mid=(l(p)+r(p))>>1;
	
	long long val=0;
	if(l<=mid) val=max(val,ask(l,r,p<<1));
	if(r>mid) val=max(val,ask(l,r,p<<1|1));
	return val;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>h[i];
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) f[i]=a[i];
	build(1,1,n);
	for(int i=1;i<=n;i++){
		f[i]=ask(1,h[i],1)+a[i];
		change(1,h[i],f[i]);
	}
	for(int i=1;i<=n;i++) ans=max(ans,f[i]);
	cout<<ans<<endl;
	return 0;
}

---

区间动态规划

石子合并

以求最小分数为例，求最大分数的方法与之类似。

显然，一个区间 \([l,r]\) 一定是由 \([l,k]\) 和 \([k+1,r]\) 转移到的\((l \le k < r)\)。这就意味着两个长度较短的区间上的信息想一个长度较长的区间发生了转移，所以，我们可以把区间长度作为阶段。

那么我们应该如何处理环形呢？只需要将给定的序列 \(a\)，复制一份并接在 \(a\) 的末尾即可。

状态：\(f_{i,j}\) 表示将 \([l,r]\) 这个区间内的石子全部合并得到的最小分数。

阶段：区间的长度。

转移：\(f_{l,r}=\underset{l \le k <r}{min}\{f_{l,k}+f_{k+1,r}\}+\sum^r_{i=l}a_{i}\)。

边界：\(\forall i \in [1,2 \times n],f_{i,i}=0\)，其余均为无穷大。

目标：\(\underset{1 \le i \le n}{min}\{f_{i,i+n-1}\}\)。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[500],sum[500],ans,f[500][500];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i+n]=a[i];
	}
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=(n<<1);i++){
		sum[i]=sum[i-1]+a[i];
		f[i][i]=0;
	}
	for(int i=2;i<=n;i++){
		for(int l=1;l+i-1<=(n<<1);l++){
			int r=l+i-1;
			for(int k=l;k<r;k++){
				f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
			}
			f[l][r]+=sum[r]-sum[l-1];
		}
	}
	ans=0x3f3f3f3f;
	for(int i=1;i<=n;i++){
		ans=min(ans,f[i][i+n-1]);
	}
	cout<<ans<<endl;
	memset(f,0xcf,sizeof(f));
	for(int i=1;i<=(n<<1);i++) f[i][i]=0;
	for(int i=2;i<=n;i++){
		for(int l=1;l+i-1<=(n<<1);l++){
			int r=l+i-1;
			for(int k=l;k<r;k++){
				f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]);
			}
			f[l][r]+=sum[r]-sum[l-1];
		}
	}
	ans=-1;
	for(int i=1;i<=n;i++){
		ans=max(ans,f[i][i+n-1]);
	}
	cout<<ans<<endl;
	return 0;
}

标签：underset,le,子段,int,max,笔记,序列,动态,规划
From： https://www.cnblogs.com/ZnHF/p/17984889

相关文章

  • 狂神说Java Web学习笔记_Cookie&Session
    Cookie,Session保存会话的两种技术，Cookie（客户端技术），Session（服务端技术）Cookie服务器端设置token，从客户端获取tokenCookie[]cookies=req.getCookies();//从客户端获取cookiecookie.getName();//获取cookie名字cookie.getValue();//获取cookie值Cookiecookie=newCoo......
  • 【学习笔记】Python 环境隔离
    目录前言venvvenv环境管理venv包管理virtualenv以及virtualenvwrapper安装virtualenvwrapper环境管理virtualenvwrapper包管理condaconda环境管理conda包管理总结参考资料Python作为最常用的脚本语言，有着非常丰富的第三方库，但是这也导致了Python的环境管理非常必要。......
  • react antd的Table中，如何动态的改变表格数据
    在ReactAntd中，如果您改变了Table组件的数据源（dataSource），Table会自动重新渲染以反映新的数据。因此，只要您在状态或props中正确更新数据源，Table就会自动更新。以下是一个示例代码片段，展示如何使用React状态（state）和按钮来更改数据源并更新Table组件：importReact,{useState}fr......
  • 应用规划
    依托平台的可伸缩架构，所有应用都可以有如下模式和版本（具体产品有那些版本看官网）：产品目录（陆续更新中）1、人力资源板块：人力资源系统及其扩展（如绩效管理、职称评审等）、在线培训、在线考试、知识管理、人才盘点、专家管理、证照管理2、市场管理板块：CRM 招投标管理3、行政管理板块：OA、会......
  • 整体发展规划
    终极目标：  基于平台+应用的模式构建组织内部所有系统组织形式：  平台隶属于北京智诚宏图科技有限公司  各个应用由各个小而美的公司承担总体战略：  统一战线，联合尽可能多资源市场发展策略：  1、“星星之火，可以燎原”：以某个应用切入用户内部系统，逐步扩展替换。  2、......
  • 运输层的TCP与UDP协议(学习笔记)
    一、运输层1.逻辑通信结构2.端口号、复用与分用二、TCP与UDP的区别1.概览图2.用户数据报协议UDP(UserDatagramProtocol)UDP面向应用层报文，可以在任何时候发起传输（无连接），向上层提供不可靠传输服务，即如果传输过程中出现误码，也不会触发重传。可以支持一对一、......
  • 人工智能(第3版) 第三章—学习笔记
    人工智能(第3版)第三章—学习笔记知情搜索（informedsearch，也称有信息搜索）利用启发式方法，通过限定搜索的深度或宽度来缩小问题空间。3.0引言介绍了本章的主要内容与几个重要的概念。3.1启发式方法乔治·波利亚——“启发式方法之父”​启发式方法的目的是大幅度减少到......
  • [Java]静态代理、动态代理（基于JDK1.8）
    【版权声明】未经博主同意，谢绝转载！（请尊重原创，博主保留追究权）https://www.cnblogs.com/cnb-yuchen/p/18002823出自【进步*于辰的博客】参考笔记一，P83；笔记二，P75.4。目录1、静态代理1.1概述1.2静态代理的两种形式1.2.1面向接口1.2.2面向继承2、动态代理2.1什么是动态代......
  • 寒假NOIP突破营笔记
    Day1枚举和搜索某些题的正解其实就是暴力，但加了一些优化三连击：暴力枚举即可DNA序列：\(O(nk)\)做法可以直接过；因为字符集大小只有\(4\)，也可以使用哈希转为四进制统计\(O(n)\)栅栏：二分答案+搜索+剪枝k短路：A*：启发式搜索的一种，定义起点\(s\)，终点\(t\)，从起点（初始状态）开始的......
  • VITS课程学习笔记
    课程地址，https://www.bilibili.com/video/BV1wV411j7zG/?spm_id_from=333.788&vd_source=1eb6e5015a1f70daa97080d8ee786d5d VITS，VariationalInferencewithadversariallearningforend-to-endText-to-Speech论文，VITS:ConditionalVariationalAutoencoderwithAd......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99