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

线性动态规划-经典例题

经典例题

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

【思路点拨】

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

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

    内在原理是 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;	
}

相似例题：木棍加工

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

#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≤103subtask1: n\leq 10^3

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

subtask2:n≤105subtask2: n\leq 10^5

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

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

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

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

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

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

当 Ai≠BjA_i \ne B_j 时，F[i,j]=F[i−1,j]F[i,j]=F[i-1,j]

当 Ai=BjA_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(nm2)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≤3000,m≤3000subtask2: n\leq 3000 ,m\leq 3000

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

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

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

我们把满足 0≤k<j,Bk<Ai0\leq k<j,B_k<A_i 的 k 构成的集合称为 F[i,j]F[i,j] 进行状态转移时的决策集合，记为 S(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≤j≤mmax(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尼克的任务

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

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

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

  1. 如果时刻 ii 没有任务： fi=fi+1+1f_i=f_{i+1}+1
  2. 枚举时刻 ii 开始的所有任务 jj (pj==i)(p_j==i)，保留最优值： fi=max(fpj+tj)f_i = max(f_{p_j+t_j})

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

每个任务只会被枚举一次，时间复杂度为 O(n+k)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;
}

例4. P1717钓鱼

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

分析

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

解法1：贪心

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

枚举鱼塘 O(n)O(n)，时间依次递减 O(12h)O(12h)，每次选择最多的鱼的鱼塘（堆优化）O(log⁡i)O(\log i)，那么整体时间复杂度就是 O(n×12h×log⁡n)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：动态规划

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

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

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

即得到 dpdp 转移方程 ：$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]dp[i][j] 初始化为0，答案就是： max(dp[i][j])max(dp[i][j])

时间复杂度： O(n∗12h∗12h)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∗mn*m 二维数字网格，从起点 (1,1)(1,1) 向下、向右走到终点，再从终点走到起点(方向相反)，路径不相交，求经过路径上数字和的最大值。

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

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

例7. P4677山区建小学

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

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

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

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

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

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

例8. P6304[eJOI2018]山

例9.P1279 字串距离

例10. P2051 [AHOI2009] 中国象棋

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

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

学习完毕

{{ select(1) }}

  • YES
  • NO
  1. 关于
  2. 联系我们
  3. Language
  4. 兼容模式
  5. 主题
  3. Worker 0 in 87ms
  4. Powered by Hydro v4.19.1 Modified by byx QQ465039728
  5. 陕ICP备2023000766号