C++ 代码

// 第一问：最长不下降子序列长度，不再赘述。

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

// 贪心：
// 用如下方式维护数组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的大小没有增加）。
// 证毕！

// 作者：玖梦づ
// 链接：https://www.acwing.com/solution/content/6746/
// 来源：AcWing
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//明显第一问就是找一个最长上升子序列，第二问的话问的是
//找最少的不上升子序列，能够覆盖所有数，

//策略
//1.若x大于s中每一个数，则新建一个不上升子序列，放入x;
// 2.否则，找到s中大于等于x的最小的数，将其替换。
// 由于s每次增加长度时，增加的数必然大于其前面s中的任何一个数；且每次替换时，不改变x与被替换数左右相邻两数的相对大小关系，故s必然维持单调递增。则s即为原序列的最长上升子序列。

#include<iostream>
#include<algorithm>

using namespace std;

const int N=1010;

int n;
int q[N];
int f[N], g[N];//维护所有不下降子序列的最后一个最小的那个元素

int main()
{
    while(cin>>q[n]) n++;//这道题很贱，没有告诉你有多少个数据

    int res=0;
    for(int i=0; i<n; i++)
    {
        f[i]=1;
        for(int j=0; j<i; j++)
            if(q[i]<=q[j])
                f[i]=max(f[i], f[j]+1);
        res=max(res, f[i]);
    }

    cout<<res<<endl;

    int cnt=0;//用来记录序列的数量
    for(int i=0; i<n; i++)
    {
        int k=0;//维护g数组
        while(k<cnt && g[k] < q[i]) k++; //找到大于等于q[i]的末尾元素最小的序列，其实贪心就贪在这了，为什么要去祸害人家大的
        g[k]=q[i];//把这个序列的最小值替换;
        if(k >= cnt) cnt++; //找不到则另起炉灶
    }

    cout<<cnt<<endl;

    return 0;
}