线性动态规划-经典例题

ID: 385

客观题

尝试: 7

已通过: 7

难度: 2

上传者:

boya

标签>

线性dp

经典例题

例1：[NOIP1999 普及组] 导弹拦截

【思路点拨】

（1）一套拦截系统最多可以拦截多个导弹，就是求一个序列的最长不上升子序列，暴力 $O(N^2)$ 会超时，利用二分优化到 $O(n\log {n})$ （经典模型里有思路）。

（2）拦截所有导弹最少的拦截系统数量，可以贪心去求，用一个数组记录每一个系统拦截的最低高度，新来一个导弹，应该优先让能够拦截并且高度最低系统拦截（高度高的系统有能力拦截更高的），如果都无法拦截就新增加一套。复杂度是 $O(N^2)$ 。实际本问就是求最长上升子序列长度，那么二分优化 $LIS$ 就可以。

    内在原理是 Dilworth 定理：
    对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。
    对偶形式亦真：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目 。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N];
int b[N];
int main()
{
	int t;
	while(scanf("%d",&t)!=EOF)a[++n]=t;
	int len=0;
	memset(b,0,sizeof(b));
	for(int i=1;i<=n;i++)
	{
		int pos=0;
		for(int j=30;j>=0;j--)
			if((pos+(1<<j))<=len && b[pos+(1<<j)]>=a[i])
				pos+=(1<<j);
				//b数组是下降序列，在下降序列里寻找第一个小于a[i]的位置 
		pos=pos+1;
		if(pos<=len)b[pos]=a[i];
		else b[++len]=a[i];
	}
	cout<<len<<endl;  
	int num=0;
	memset(b,0,sizeof(b));
	for(int i=1;i<=n;i++)
		{
			int pos=0;
			for(int j=30;j>=0;j--)
				if((pos+(1<<j))<=num && b[(pos+(1<<j))]<a[i])   
					pos+=(1<<j);
			pos++;   //b数组是上升序列，在上升序列里寻找第一个大于等于a[i]的位置 
			if(pos<=num)b[pos]=a[i];
			else b[++num]=a[i];
		}
	cout<<num;	
}

相似例题：木棍加工

偏序，按照 $L$ 从小到大排序，如果 $W$ 递减，就不需要停下来准备，也就是分成最少的几条 $W$ 下降的链，根据Dilworth 定理就等于最长的反链长度，也就是 $W$ 的严格上升子序列长度。

#include <bits/stdc++.h>
using namespace std;
const int N=5e3+10;
struct node
{
	int l,w;
}stick[N];
int n;
bool cmp(node a,node b)
{
	return a.l>b.l;
}
int ans[N],num;  //维护一个不下降序列 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>stick[i].l>>stick[i].w;
	//按照l从大到小排序 
	sort(stick+1,stick+n+1,cmp);
	//根据Dilworth定理，最少链的划分数目=最长反链的长度
	//也就是 求w中最长严格上升长度，转化为LIS
	num=1;
	ans[1]=stick[1].w;
	for(int i=2;i<=n;i++)
	{
		int pos=lower_bound(ans+1,ans+num+1,stick[i].w)-ans;
		if(pos<=num)ans[pos]=stick[i].w;
		else ans[++num]=stick[i].w;
	}
	cout<<num;
	return 0;	
}

变形例题：P1439 【模板】最长公共子序列

$subtask1: n\leq 10^3$

可以使用 $LCS$ 普通模型完成，设 $F[i,j]$ 表示前缀子串 $A[1...i]$ 与 $B[1...j]$ 的“最长公共子序列”的长度，时间复杂度 $O(nm)$ 。

$subtask2: n\leq 10^5$

要巧用 $1\dots n$ 的排列这个限制信息，对于第一个排列 $A[i]$ ,可以再 $B[]$ 中找到其对应的位置 $P[i]$ ，即 $P[i]$ 表示 $A[i]$ 在 $B[]$ 中的位置，那么 $P[i]$ 中最长上升序列就是答案。

画出图来， $i$ 是递增的，如果 $P[i]$ 也递增，那么就不会交叉，不交叉的数量越多越好，这就是 $LIS$ .

例2：LCIS(最长公共上升子序列)

题意：对于两个数列 $A$ 和 $B$ ，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列。

$subtask1 : n \leq 500 ,m \leq 500$

【解析】： $F[i,j]$ 表示 $A[1...i]$ 与 $B[1...j]$ 可以构成的 以 $B_j$ 为结尾 的 $LCIS$ 的长度。

当 $A_i \ne B_j$ 时， $F[i,j]=F[i-1,j]$

当 $A_i = B_j$ 时， $F[i,j]=max_{ 0 \leq k <j,B_k < B_j } \{ F[i-1,k]\} +1$ = $F[i,j]=max_{ 0 \leq k <j,B_k < A_i } \{ F[i-1,k]\} +1$

上面的转移过程可以用三重循环进行计算,时间复杂度为 $O(nm^2)$ 。

	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i]==b[j])
			{
				for(int k=0;k<j;k++)
					if(b[k]<a[i])
						f[i][j]=max(f[i][j],f[i-1][k]+1);
			}
			else f[i][j]=f[i-1][j];

对于例题CF10D LCIS，求LCIS长度，还要输出一个LCIS方案.

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N=505;
int n,m;
int a[N],b[N],pre[N][N];
int dp[N][N];
//dp[i][j]表示以b[j]结尾的最长公共上升子序列长度 
//=dp[i-1][j]
//if(a[i]==b[j]) =max(dp[i-1][k]+1 ,b[k]<b[j],pre[j]=k)
// pre[j][1~dp[i][j]] 以b[j]结尾，a[i]和b[j]最长公共上升子序列 
int main() {
	cin>>n;
	for(int i=1; i<=n; i++)cin>>a[i];
	cin>>m;
	for(int i=1; i<=m; i++)cin>>b[i];
	int maxlen=0,endpos;
	a[0]=b[0]=-1;
	memset(pre,0,sizeof(pre));
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) 
		{
			if(a[i]==b[j]) 
			{
				for(int k=0; k<j; k++)
					if(b[k]<b[j]) {
						if(dp[i-1][k]+1>dp[i][j]) {
							dp[i][j]=dp[i-1][k]+1;		
						for(int p=1;p<=dp[i-1][k];p++)
							pre[j][p]=pre[k][p];					
						pre[j][dp[i][j]]=b[j];		
							}
						if(dp[i][j]>maxlen) {
								maxlen=dp[i][j];
								endpos=j;
							}
						}
			}
			else dp[i][j]=dp[i-1][j];
		}
	cout<<maxlen<<endl;
	for(int p=1;p<=maxlen;p++)
		cout<<pre[endpos][p]<<" ";
	return 0;
}

$subtask2: n\leq 3000 ,m\leq 3000$

数据规模扩大，需要进行优化处理。

在第二层循环 j 从 1 增大到 m 时，第一层循环 i 是一个定值，这使得条件 $B_k <A_i$ 是固定的。因此，当变量 j 增加 1 时，k 的取值范围从 $0\leq k <j$ 变为 $0 \leq k < j+1$ ，即整数 j 可能会进入新的决策集合。

也就是我们只需要 O(1) 地检查条件 $B_j<A_i$ 是否满足，已经在决策集合中的数则一定不会被去除。

我们把满足 $0\leq k<j,B_k<A_i$ 的 k 构成的集合称为 $F[i,j]$ 进行状态转移时的决策集合，记为 $S(i,j)$ 。

$S(i,j+1)= \begin{cases}S(i,j), & if & B_j>=A_i \\S(i,j)\cup \{j\}, & if & B_j<A_i \end{cases}$

上面的转移只要两重循环就可以求解,最终目标为 $max(F[n,j]),1\leq j \leq m$ 。

	for(int i=1;i<=n;i++){
		//val表示决策集合S(i,j)中f[i-1][k]的最大值 
		int val=0;
		for(int j=1;j<=m;j++)
		{
			if(a[i]==b[j])f[i][j]=val+1;
			else f[i][j]=f[i-1][j];
			
			//j即将增大j+1,检查j能否进入新的决策集合 
			if(b[j]<a[i])val=max(val,f[i-1][j]); 
		}
	}

在实现状态转移方程时，要注意观察决策集合的范围随着状态的变化情况。

对于“决策集合中的元素只增不减”的情景，就可以像本题一样维护一个变量来记录决策集合的当前信息，避免重复扫描，把转移复杂度降低一个量级。

例3. P1280尼克的任务

题意简化 ：给定 $k$ 个任务，每个任务持续时间为 $[p_j,p_j+t-1]$ ，时刻 $i$ 如果有任务尼克可以选择一个任务，如果时刻 $i$ 没有任务，尼克可以空闲，询问尼克 $[1,n]$ 时间段内最长休息时间。 $1 \leq n,k \leq 10^4$

分析：可以将任务按照开始时刻分类(排序)，如果时刻 $i$ 没有任务那就休息，如果有任务那可以枚举此时刻开始的所有任务，保留最大值。

那么可以定义状态： $f_i$ 表示时间 $[i...n]$ 最大休息时间。

如果时刻 $i$ 没有任务： $f_i=f_{i+1}+1$
枚举时刻 $i$ 开始的所有任务 $j$ $(p_j==i)$ ，保留最优值： $f_i = max(f_{p_j+t_j})$

转移是时间序列上线性的，按时间从大到小，线性dp基本模型。初始 $f_i=0$ ; 结果 $ans=f_1$ 。

每个任务只会被枚举一次，时间复杂度为 $O(n+k)$ .

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+10;
int n,k,f[N];
vector<int>ed[N];  
//ed[网格 表示时间 i 开始的所有任务对应的结束时间 
//读入的时候，就按时间分类了 
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=k;i++)
	{
		int p,t;
		cin>>p>>t;
		ed[p].push_back(p+t);  //p开始，p+t-1结束 p+t就空闲了 
	} 
	for(int i=n;i;i--)   //f[i] 表示[i...n]时间最大 要倒着进行 
	{
		if(ed[i].size()==0)  //没有 i时刻开始的任务
			f[i]=f[i+1]+1; 
		else
		{
			for(int j:ed[i])  //j表示这项任务结束后下一个时刻 
				f[i]=max(f[i],f[j]); 
		}
	} 
	cout<<f[1];
	return 0;
}

题意简化：给定 $H$ 的小时， $n$ 个鱼塘，第 $i$ 个鱼塘从开始钓鱼,开始每 $5$ min 钓 $fi$ ，每过 $5$ min 钓鱼量减少 $d_i$ ，依次递减。从第 $i$ 个鱼塘走到第 $i+1$ 个鱼塘需要 $5*t_izhuangt第一个鱼塘，最后可以停在任意一个鱼塘。询问$ H$ 小时的能钓到最多的鱼。 $1 \leq H \leq 16, 2 \leq n \leq 25$

分析

题目中都是以 5min 作为最小计算单位时间计算的，那么把所有时间都转化为多少个 5min， $H \rightarrow 12*H$ ，最优性问题常见的解决思路，就是贪心（问题本身要符合全局最优”）、动态规划（问题能够定义成分阶段“最优子结构”的形式）。

解法1：贪心

本质上，就是除了路上花的时间外，把时间分配到能钓到鱼多的鱼塘。枚举最后停留的鱼塘 $i$ ，除去路上花的时间，每一个 5min,选择 $1-i$ 鱼塘的鱼量最多的鱼钓鱼，直到时间用完，或没有鱼了。 选择当前最多鱼塘，可以使用大根堆进行优化。

枚举鱼塘 $O(n)$ ，时间依次递减 $O(12h)$ ，每次选择最多的鱼的鱼塘（堆优化） $O(\log i)$ ，那么整体时间复杂度就是 $O(n \times 12h \times \log n )$ .

参考代码：

#include <bits/stdc++.h>
using namespace std;
int n,h,f[26],t[26],d[26];
int sol(int num)//只钓前num个鱼塘的鱼，最后停在第num个鱼塘
  //返回最多的鱼 
{
	int tim=h*12;
	int ret=0; 
	for(int i=1;i<num;i++)tim-=t[i];
	priority_queue<pair<int,int> >que;  //创建一个大根堆，以当前鱼量为关键字，同时保留递减量
	for(int i=1;i<=num;i++)
		que.push({f[i],d[i]});
	while(tim>0)  //每过1个5min都挑一个鱼最多的鱼塘钓，此时不考虑路上时间
	{
		int fish=que.top().first,dert=que.top().second; que.pop();
		if(fish<=0)break;   //没鱼了
		ret+=fish;
		que.push({fish-dert,dert});
		tim--;
	} 
	return ret;	
}
int main()
{
	cin>>n;
	cin>>h;
	for(int i=1;i<=n;i++)cin>>f[i];
	for(int i=1;i<=n;i++)cin>>d[i];
	for(int i=1;i<n;i++)cin>>t[i];
	int ans=0;
	for(int i=1;i<=n;i++)
		ans=max(ans,sol(i));  //只钓1-i内的鱼
	cout<<ans;
	return 0;
}

解法2：动态规划

前 $i$ 个鱼塘，考虑第 $i$ 个鱼塘给分配多少个 $5min$ ，可以调到最多的鱼，给前 $i$ 个鱼塘分配 $j$ 个 $5min$ , $i$ 是阶段， $j$ 看做“资源”（“资源规划使得最优”），本质上是“泛化”的背包问题。

那么定义状态： $dp[i][j]$ 前i个湖停留 $j$ 个 5分钟所能钓到最多的鱼的数量

给第 $i$ 个鱼塘分配 $k$ 个 5分钟, 第 $i$ 个鱼塘能钓到的鱼就是 $f_i+ (f_i-d_i)+...+(f_i-(k-1)*d_i)=\frac{(2*f_i-(k-1)*d_i)*k}{2}$ ,当然 $f_i-(k-1)*d_i>=0$ ,否则会钓到负数鱼数量，肯定就不对了。

即得到 $dp$ 转移方程： $dp[i][j]=max(dp[i-1][j-t_{i-1}-k]+k*(2*f_i-(k-1)*d_i)/2)，fi-(k-1)*di>=0$

$dp[i][j]$ 初始化为0，答案就是： $max(dp[i][j])$

时间复杂度： $O(n*12h*12h)$

参考代码：

  #include <bits/stdc++.h>
  using namespace std;
  const int N=26+1,H=17+1;
  int n,h,f[N],d[N],t[N];
  int dp[N][12*H];
  int main()
  {
  	cin>>n>>h;
  	for(int i=1;i<=n;i++)cin>>f[i];
  	for(int i=1;i<=n;i++)cin>>d[i];
  	for(int i=1;i< n;i++)cin>>t[i];
  	memset(dp,-1,sizeof(dp));   //判断是否有不合法的情况 
  	int ans=0;
  	dp[0][0]=0; 
  	for(int i=1;i<=n;i++)
  	{
  		for(int j=t[i-1];j<=12*h;j++)  //要能走到第i个鱼塘，避免j-t[i-1]是负数 
  		{
  			dp[i][j]=dp[i-1][j-t[i-1]];  //不钓鱼
  			for(int k=1;k<=j-t[i-1];k++)  //钓 k个 5分钟的鱼 
  				if( f[i]-(k-1)*d[i]>=0 && dp[i-1][j-t[i-1]-k]!=-1) //鱼够  且前面合法 
  				{
  					dp[i][j]=max(dp[i][j],dp[i-1][j-t[i-1]-k]+(2*f[i]-(k-1)*d[i])*k/2);
  				} 
  			ans=max(ans,dp[i][j]);
  		}		
  	}
  	cout<<ans;
  	return 0;
  }

例5. P1541[NOIP2010 提高组]乌龟棋

例6. P1006[NOIP2008 提高组]传纸条

题意简化：给定一个 $n*m$ 二维数字网格，从起点 $(1,1)$ 向下、向右走到终点，再从终点走到起点(方向相反)，路径不相交，求经过路径上数字和的最大值。

分析：首先“贪心走一条路，再走另外一条路” 是错误的，因为：第一路可能最大，第二天路小，而有可能两条都比较大，但总和更大。

可以两条路一起从起点走到终点，那么定义： $f[x1][y1][x2][y2]$ 表示第一条走到 $(x1,y1)$ ,第二条路走到 $(x2,y2)$ 经过的数字和最大。发现状态有冗余，因为 $x1+y1=x2+y2$ ，那么可以优化掉一维状态

例7. P4677山区建小学

题意简化：给定 $n$ 个村庄的位置（线性），建 $m$ 所学校，求所有村到附近一所的距离和的最小值。

分析：如果只建 $1$ 所学校，根据中位数的性质，学校应该建在 $n$ 所学校中位数的位置; 如果建 $2$ 所学校，可以枚举断点 $i$ ， $[1,i]$ 和 $[i+1,n]$ 各建一所学校，各自建在中位数处，如果暴力求时间复杂度为 $O(N^2)$ ,可以利用“前缀和”优化,时间复杂度优化到 $O(N)$ ，例题“Boyacoding "P1006. 建学校”

当 $m>2$ 就需要利用动态规划求解。

定义 $f[i][j]$ 表示前 $i$ 个村庄建 $j$ 所学校总距离最小值

$f[i][j]=min\{f[k][j-1]+cost(k+1,i)\}$ ，其中 $cost(k+1,i)$ 表示第 $k+1$ 至 $i$ 建一所学校的最小花费。

时间复杂度为 $O(n^2m)$ .

例8. P6304[eJOI2018]山

例9.P1279 字串距离

例10. P2051 [AHOI2009] 中国象棋

例11. P1018 [NOIP2000 提高组] 乘积最大

例12. P2516 [HAOI2010] 最长公共子序列

学习完毕

A. YES

B. NO

#edu2003. 线性动态规划-经典例题

经典例题

例1：[NOIP1999 普及组] 导弹拦截

相似例题：木棍加工

变形例题：P1439 【模板】最长公共子序列

例2：LCIS(最长公共上升子序列)

例3. P1280尼克的任务

例4. P1717钓鱼

例5. P1541[NOIP2010 提高组]乌龟棋

例6. P1006[NOIP2008 提高组]传纸条

例7. P4677山区建小学

例8. P6304[eJOI2018]山

例9.P1279 字串距离

例10. P2051 [AHOI2009] 中国象棋

例11. P1018 [NOIP2000 提高组] 乘积最大

例12. P2516 [HAOI2010] 最长公共子序列

学习完毕

状态

开发

支持

#edu2003. 线性动态规划-经典例题

线性动态规划-经典例题

经典例题

例1：[NOIP1999 普及组] 导弹拦截

相似例题：木棍加工

变形例题：P1439 【模板】最长公共子序列

例2：LCIS(最长公共上升子序列)

例3. P1280尼克的任务

例4. P1717钓鱼

例5. P1541[NOIP2010 提高组]乌龟棋

例6. P1006[NOIP2008 提高组]传纸条

例7. P4677山区建小学

例8. P6304[eJOI2018]山

例9.P1279 字串距离

例10. P2051 [AHOI2009] 中国象棋

例11. P1018 [NOIP2000 提高组] 乘积最大

例12. P2516 [HAOI2010] 最长公共子序列

学习完毕

状态

开发

支持

还没有账户？

登录