题目

\(\\\)
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统
\(\\\)
经典的DP,适合打好基础
\(\\\)

第一问

求最长不下降子序列
定义\(dp_i\) 为以第\(i\)个导弹高度为结尾，拦截的最多的导弹
\(h[i]\)为第\(i\)个导弹高度
\(\\\)
所以根据dp的通常思考方式，寻找\(dp_i\)之间的关系
\(\\\)
如果\(\exist j<i 且 h[j]>h[i]\) 那么这两个导弹就能被同一个导弹拦截系统
\(\\\)
同理\(\exist j<i 且 h[j]>h[i]\) 那么\(dp_i=dp_j+1\)
\(\\\)
此时以第\(j\)个导弹高度为结尾的序列长度为\(dp_j\)，而\(h[j]>h[i]\)
也可以拦截第\(i\)个导弹
\(\\\)
而\(dp_i可以由多个dp_j得到，所以\displaystyle dp_i=max_{j<i, h[j]>h[i]} (dp_i,dp_j+1)\)

第二问

求最少的不下降子序列个数
贪心，当前已有的系统拦截不到，就增加系统
定义\(dp_i\)为第i个导弹高度为结尾的第\(dp_i\)个系统
\(\\\)
如果\(\exist j<i 且 h[j]<h[i]\) 那么这两个导弹就不能被同一个导弹拦截系统，需要新开一个系统,且新系统的拦截最后一个导弹为h[i]
如果\(\exist j<i 且 h[j]>h[i]\) 那么这个导弹就可以被之前拦截h[j]的导弹拦截，就不需要开新系统
\(\\\)
同理\(\exist j<i 且 h[j]<h[i]\) 那么\(dp_i=dp_j+1\)
\(\\\)
而\(dp_i可以由多个dp_j得到，所以\displaystyle dp_i=max_{j<i, h[j]<h[i]} (dp_i,dp_j+1)\)
\(\\\)
--小疑问：可能会有人问，为什么求最少的不下降序列个数反而还要取max
答：这样取max才能使每一个导弹被拦截

\(\\\)

CODE

#include<cstring>
#include<iostream>

using namespace std;
int n;
int m[100000+10];
int f[100000+10];
int ans[100000+10];
int main(){
	ios::sync_with_stdio(0);
	int a;
	int len=0;
	memset(ans,0,sizeof(ans));
	while(cin>>a){
		m[++len]=a;
		f[len]=1;
	} 
	int maxx=0; 
	for(int i=2;i<=len;++i){
		for(int j=1;j<i;++j)
			if(m[i]<=m[j]) 
				f[i]=max(f[i],f[j]+1);
		maxx=max(f[i],maxx);
	}
	cout<<maxx<<endl;
	maxx=0;
	memset(f,1,sizeof(f));
	
	for(int i=1;i<=len;++i){
		f[i]=1;
		for(int j=1;j<i;++j)
			if(m[j]<m[i])
				f[i]=max(f[i],f[j]+1);
		maxx=max(maxx,f[i]);//有可能后面的导弹已经被前面已有的系统拦截了，不需要开新系统，而此时找到的最大值即是刚好拦截所有导弹的系统数量
	}
	cout<<maxx<<endl;
	return 0;
}

以上的code可以过1e5级别的数据

而此题可以考虑优化

优化

1.第一问

根据\(\displaystyle dp_i=max_{j<i, h[j]>h[i]} (dp_i,dp_j+1)\)

\(\\\)
我们有一定的时间在寻找\(max(dp_j+1)\),这导致了我们每次寻找时的复杂度为\(O(N)\)
根据题目的复杂度要求，我们应该考虑\(log_{2}N\)复杂度的寻找方法
对于\(\forall dp_j\in[0,n] \ and \ n<1e5\)
而且我们只需要最大值
\(\\\)
这时如果我们利用桶排序的思想，就能快速查找，并且存最大值

令\(f[x]\)为长度为x的最长不上升子序列的末端高度
\(\\\)
对于\(\forall x>1 , \exist y<x,f[x]<f[y]\)(单调递减)
\(\\\)
所以当我们考虑\(h[i]\)时，我们只需要在已知长度中找\(f[j]<=h[i](j为符合该条件的最大值)，f[j+1]=h[i]\)
\(\\\)
而由于这种序列是单调递减，所以二分查找就可以，复杂度就降到\(O(log_2N)\)

第二问

\(\displaystyle dp_i=max_{j<i, h[j]<h[i]} (dp_i,dp_j+1)\)
令\(f[x]\)为第x个系统的拦截的末端高度
\(\\\)
对于\(\forall x>0, \exist y>x,f[x]<f[y]\)(单调递增)

所以对于\(h[i]\),开一个新系统，我们只需要考虑，不\(\exists x，f[x]>h[i]\)，此时没有系统拦截的高度超过当前导弹，所以需要一个新系统

#include<bits/stdc++.h>

using namespace std;
int n=0;
const int maxn=1e5+10;
int t;
int h[maxn],f[maxn];

int main(){
    while(~scanf("%d",&h[++n])); --n;
	t=1;memset(f,0,sizeof(f));
	//f[i]表示长度i的序列结尾的高度 
	for(int i=1;i<=n;++i){
		int l=1,r=t;//当前长度的范围
		
		while(l<=r){//查找该高度可以拼接的最长长度 
			int mid=(l+r)>>1;
			if(f[mid]>=h[i]) l=mid+1;
			else r=mid-1;
		}
		//最后二分找到的 f[l]<h[i] && f[r]>=h[i] && r+1=l 
		//所以 f[l]=h[i]
		//若长度增加,r=t,l=t+1; //最大长度增加
		if(l>t)	t=l; 
		f[l]=h[i];//长度l的最长不上升序列结尾是h[i] 
	}
	printf("%d\n",t);
	t=0;memset(f,0,sizeof(f));
	for(int i=1;i<=n;++i){
		int l=0,r=t;//当前系统数范围
		while(l<=r){//查找该高度可以拼接的系统，找不到，就新增系统 
			int mid=(l+r)>>1;
			if(f[mid]<h[i]) l=mid+1;
			else r=mid-1;
		}
		if(l>t) t=l;
		f[l]=h[i]; 
	} 
	printf("%d\n",t);
	return 0;
}