【正经题解】导弹拦截

读入就是用变量记一下数组当前长度，只要输入 $a[++n]!=EOF$ ,就一直读下去。
很明显，第一个问题是让求最长不升子序列，首先我们开两个 dp 数组，第一个 dp 数组求第一问，第二个求第二问，再开两个变量分别统计答案。我们先把第一项复制成 a 数组的第 1 项，无论如何至少你能打下来一个，所以 $len_1$ = 1，接下来我们从第二个数组元素循环，只要小要小于 dp 数组的前一项就 $len_1$ $+1$ 并且 $dp_len1$ =$a_i$ 可是我们如果发现了当前元素比 $dp$ 数组末位元素大，说明这个高度会更有潜力，因为这个高度较大，我们可以多打中几枚，我们就找到比它小（注：在 $upper$ _ $bound$ 里面 用 greater<typename> () ）的一个元素把它替换掉，这样就以 $nlogn$ 的复杂 度解决了第一个问题。
第二个问题我们试着来考虑一下，发现第二个 $dp$ 数组的第一项也可以用 $a$ 数组的第一项先管着，同样 $len$ _ $2$ $=1$ ，因为你至少要用一个系统。我们在从第二个元素扫的时候只要有一个高度比当前 $dp$ 数组最后一个系统的高度大，你就直接再加 一个系统，因为前一个系统拦截不到这里。如果不是这样我们就考虑用之前用过的一个拦截系统把这个导弹给拦截下来，这意味着这个高度同样可以使我们拦截掉更多的导弹，我们就找一个高度刚好大于或者等于它的 $dp$ 数组中的一个元素给替换成当前拦截的导弹高度值。说到这里，各位不难想到这其实就是求得最长上升子序列，同样以 $nlogn$ 的时间复杂度求出了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 1000010
using namespace std;
typedef long long ll;
ll a[maxn],n=1,dp1[maxn],dp2[maxn],len1,len2;
inline void write(ll x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int main(){
	while(cin>>a[n]){
		n++;
	}
	n--,len1=1,len2=1;
	dp1[1]=a[1],dp2[1]=a[1];
	for(ll i=2;i<=n;i++){
		if(a[i]<=dp1[len1]){
			dp1[++len1]=a[i];
		}
		else{
			ll k1=upper_bound(dp1+1,dp1+len1+1,a[i],greater<ll>())-dp1;
			dp1[k1]=a[i]; 
		}
		if(a[i]>dp2[len2]){
			dp2[++len2]=a[i];
		}
		else{
			ll k2=lower_bound(dp2+1,dp2+len2+1,a[i])-dp2;
			dp2[k2]=a[i];
		}
	}
	write(len1);
	puts("");
	write(len2);
	return 0;
}