[NOIP1999 普及组] 导弹拦截

思路：

（1）条件：n个数

（2）问题：

1. 求最长递减子序列长度；
2. 最少拆分为多少个递减子序列

（3）分析：

1. dp : O(n^2);
2. f[i]描述长度为i的序列尾部最小值，每次用二分找到新值a[i]可以更新哪个长度，并更新即可；  : O(nlog(n));
3. dilworth定理：最长链元素数目等于反向链最小划分数目；

代码：

#include 
using namespace std;
const int N=100010;
int n,ans,a[N],f[N];//这里把f数组与len数组合并了
int main()
{
	cin.tie(0);
	cout.tie(0);//必须加速优化
	int x;
	while(cin>>x)a[++n]=x;
	memset(f,0x3F,sizeof(f));//初始化为极大值
	reverse(a+1,a+n+1);//反转
	for(int i=1;i<=n;i++)
	{
		int l=1,r=i;
		while(l//左查
		{
			int mid=(l+r)/2;
			if(f[mid]>a[i])r=mid;
			else l=mid+1;	
		}
		f[l]=min(f[l],a[i]);
		ans=max(ans,l);
	}
	cout<
	memset(f,0x3F,sizeof(f));
	reverse(a+1,a+n+1);//反转回来
	ans=0;//注意
	for(int i=1;i<=n;i++)
	{
		int l=1,r=i;
		while(l
		{
			int mid=(l+r)/2;
			if(f[mid]>=a[i])r=mid;
			else l=mid+1;	
		}
		f[l]=min(f[l],a[i]);
		ans=max(ans,l);
	}
	cout<
	return 0;
}