https://www.luogu.com.cn/problem/P1020

题目描述

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

输入导弹依次飞来的高度（雷达给出的高度数据是 ≤50000 的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

1行，若干个整数（个数 ≤100000）

输出格式

2行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出样例

输入 #1

1
389 207 155 300 299 170 158 65

输出 #1

1
2
6
2

dilworth定理 : 对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目。

并不能看懂，看了一圈下来，意思就是本题中需要多少套导弹拦截系统等于最长上升子序列的长度。

然后求一遍最长不增序列和一趟最长上升序列。两个的二分有区别，需要注意一下…当然也可以用

algorithm 里面的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
const int INF=0x3f3f3f3f;
const int MAX=100000+10;
int a[MAX],cnt,len1,len2,f[MAX]; 
int bs(int *f,int l,int r,int x){ //单增序列 
	while(l<r){
		int m=(l+r)/2;
		if(f[m]<x) l=m+1;
		else r=m;
	}
	return f[l]>=x?l-1:l;  //找到最后一个小于 x 的元素 
}
int bs2(int *f,int l,int r,int x){ //不增序列 
	while(l<r){
		int m=(l+r)/2;
		if(f[m]<=x) r=m;   //不增序列，左高右低，所以此时往左取 
		else l=m+1;
	}
	return f[l]<x?l-1:l;  //与递增不同，这里找的是最后一个大于 x 的元素 
}
int main(){
	freopen("in","r",stdin);
	len1=len2=0;cnt=0;
	while(~sf(a[cnt++]));
	cnt--;
	f[0]=-INF;
	fi(i,0,cnt){
		int x=bs2(f,0,len1,a[i]);
		f[x+1]=a[i];
		len1=max(len1,x+1);
	} 
	fi(i,0,cnt){
		int x=bs(f,0,len2,a[i]);
		f[x+1]=a[i];
		len2=max(len2,x+1);
	} 
	printf("%d\n%d",len1+1,len2+1);
	return 0;
}