codevs1044：dilworth定理

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[30010];
int a[30010];
int n;
int LIS()
{
    memset(dp,0,sizeof(dp));
    int k=0;
    dp[k++]=a[0];
    for(int i=1; i<n; i++)
    {
        if(a[i]>=dp[k-1])
        {
            dp[k++]=a[i];
            continue;
        }
        int t=lower_bound(dp,dp+k,a[i])-dp;
        dp[t]=a[i];
    }
    return k;
}
int main()
{

    n=0;
    while(scanf("%d",a+(n++))!=EOF);
    n--;
    int ans2=LIS();
    reverse(a,a+n);
    int ans1=LIS();
    cout<<ans1<<endl<<ans2<<endl;
    return 0;
}