http://www.cnblogs.com/submarine/archive/2011/08/03/2126423.html
dilworth定理的介绍
题目大意：
求一个序列的lds
同时找出这个序列最少用几个下降子序列覆盖
题解：
第一问当然非常简单，第二问不会了。。准备去搬最小路径覆盖模板
结果百度了一下发现由dilworth定理可知答案就是 lis的长度。。。跪
代码：
#include<stdio.h>
#include<string>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
int dp[];
int a[];
int n;
int LIS()
{
memset(dp,,sizeof(dp));
int k=;
dp[k++]=a[];
for(int i=; i<n; i++)
{
if(a[i]>=dp[k-])
{
dp[k++]=a[i];
continue;
}
int t=lower_bound(dp,dp+k,a[i])-dp;
dp[t]=a[i];
}
return k;
}
int main()
{ n=;
while(scanf("%d",a+(n++))!=EOF);
n--;
int ans2=LIS();
reverse(a,a+n);
int ans1=LIS();
cout<<ans1<<endl<<ans2<<endl;
return ;
}