贪心 $O(nlogn)$

（根据yxc老师的课程内容整理）

第一问：最长不上升子序列长度，不再赘述。

第二问：能覆盖整个序列的最少的不上升子序列的个数

贪心：
用如下方式维护数组s，数组长度cnt，意为cnt个不上升子序列。保存的是每一个不上升子序列中的最后一个数：
遍历原序列，对于遍历到的每一个数x：
1.若x大于s中每一个数，则新建一个不上升子序列，放入x;
2.否则，找到s中大于等于x的最小的数，将其替换。
由于s每次增加长度时，增加的数必然大于其前面s中的任何一个数；且每次替换时，不改变x与被替换数左右相邻两数的相对大小关系，故s必然维持单调递增。则s即为原序列的最长上升子序列。

即证明了：
“能覆盖整个序列的最少的不上升子序列的个数”等价于“该序列的最长上升子序列长度”
同理即有：
“能覆盖整个序列的最少的不下降子序列的个数”等价于“该序列的最长下降子序列长度”
（欲深究可研读离散数学中的Dilworth定理）

下面证明上述贪心算法的正确性：
设A为用该贪心算法得到的方案，B为最优解方案。记A的不上升子序列个数为la，B的不上升子序列个数为lb。
显然lb<=la（否则B就不是最优解）。
故只需证明la>=lb。用调整法(微调法)。
若A=B，则la=lb，显然成立。
否则（即A!=B），必然可以找到两方案中第一个(以原序列的顺序)不同之处（某数放在了不同的位置，且原序列中该数前的所有数在两方案中放的位置皆相同），将该数在两方案中所处的位置上的数(即该数本身)以及两位置之后方案中的序列相互对调，结果所得方案仍为合法解。即我们将贪心算法所得方案调整成了最优方案，且在调整过程中，方案的序列数没有增加，故la>=lb（la -> lb，且la转变为lb的过程中la的大小没有增加）。
证毕！

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

const int N=1e6+10;

int n;
int a[N];
int f[N];
int s[N];

int find(int l,int r,int x)
{
    while(l<r)
    {
        int mid=(l+r)/2;
        if(f[mid]<x)r=mid;
        else l=mid+1;
    }
    return r;
}

int main()
{
    int x;
    while(~scanf("%d",&x))if(x)a[++n]=x;

    int len=1;f[len]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(a[i]<=f[len])f[++len]=a[i];
        else f[find(1,len,a[i])]=a[i];    
    }
    printf("%d\n",len);

    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>s[cnt])s[++cnt]=a[i];
        else s[lower_bound(s+1,s+cnt+1,a[i])-s]=a[i];
    }
    printf("%d\n",cnt);

    return 0;
}