P1020 导弹拦截|二分优化DP，

学会Dilworth定理，最长上升子序列即为最少选择的分组数(覆盖原来所有导弹)

题解：https://www.luogu.com.cn/blog/w1049/solution-p1020

#include<bits/stdc++.h>
using namespace std;

const int maxn = 100010;
int len1 = 0,len2 = 0;

int a[maxn],d1[maxn],d2[maxn];
int n = 0;
int main(){
	int d;
	while(cin>>d){
		a[++n] = d;
	}
	d1[++len1] = a[1];
	d2[++len2] = a[1];
	for(int i=2;i<=n;i++){ 
		if(d1[len1] >= a[i]){ //最长不上升子序列  不上升指可以等于 
			d1[++len1] = a[i];
		}else{
			//我们需要优化d数组, 尽可能让前面的元素大,所以查找d数组中第一个小于a[i]的元素 替换它尽能让前面的元素大 
			int pos1 = upper_bound(d1+1,d1+len1+1,a[i],greater<int>()) - d1;
			d1[pos1] = a[i];
		}
		if(d2[len2] < a[i]){ //最长上升子序列 
			d2[++len2] = a[i];
		}else{ //我们需要优化d数组, 尽可能让前面的元素小,所以查找d数组中第一个小于等于a[i]的元素
			int pos2 = lower_bound(d2+1,d2+len2+1,a[i]) - d2;
			d2[pos2] = a[i];
		}
	}
	cout<<len1<<endl;
	cout<<len2;
	return 0;
} 

类似题：牛客6-汉诺塔(LIS+定理)：https://blog.csdn.net/qq_42815188/article/details/104348373