证明过程看注解即可

还可以惊奇的发现：与算法基础课的 AcWing 896. 最长上升子序列 II 维护的数组是一样的！

结论：求解最长上升子序列 和 用多少个最长不上升子序列覆盖掉整个完整序列的问题本质是完全一样的！

这个在离散数学中被称之为狄尔沃斯dilworth定理！

关于二者的联系：可以看这位同学的题解！https://www.acwing.com/solution/content/6525/

参考代码一：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int w[N], f[N], g[N], n;

/*
第一问：就是最长不上升子序列
第二问：属于贪心

    思路：用一个数组保存若干个不上升子序列结尾的数！
    猜想：我们只要考虑将每一个数放到结尾大于等于自己的数的最小值后面即可！（离自己最近）

    证明猜想的正确性：通过证明最优解A和贪心解B相等即可！
        1. A <= B：显然最优解得到的序列个数一定小于贪心解！
        2. A >= B：我们使用调整法证明

            ---------------------ax---------       贪心解
            -----------------------bx---------     最优解

            当前数为x, 由于贪心解是放到结尾大于等于自己最小值的后面，因此 b >= a

            我们将最优解和贪心解x后面的数都进行交换：
                1. 由于a >= x，因此最优解的x可以换到贪心解x的位置
                2. 由于b >= a，因此贪心解的x也可以换到最优解的位置

            因此最优解一定可以通过有限次交换，换到贪心解的位置，和贪心解相同！
            由于换的过程，序列数并没有增加，因此 A >= B 得证！

        因此得证：贪心解就是最优解！


    数组保存的不上升子序列一定是单调递增的！
        简单证明：
            原来数组：假设原来是单调递增的，大于等于x的最小的数为g[b]，
                      即 a < b < c 有 g[a] < x <= g[b] <= g[c]
              将x插入g[b]之后：g[a] < g[b] <= g[c]，仍然是单调递增的！
        通俗证明：只有当当前数找不到比自己大的序列结尾时，才会新建一个新的序列，
                  即新序列的结尾一定比所有之前序列的结尾要大！即为单调递增的！


    还可以惊奇的发现：与算法基础课的 AcWing 896. 最长上升子序列 II 维护的数组是一样的！

        结论：求解最长上升子序列 和 用多少个最长不上升子序列覆盖掉整个完整序列的问题本质是完全一样的！

*/

int main(){
    while(cin >> w[n]) n ++;

    // 最长不上升子序列
    int res = 0;
    for(int i = 0; i < n; i ++){
        f[i] = 1;
        for(int j = 0; j < i; j ++)
            if(w[j] >= w[i]) 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;
        // 找已有序列结尾大于等于自己且离自己最近的序列！第一个大于等于自己的时候即可！
        while(k < cnt && g[k] < w[i]) k ++;
        g[k] = w[i];
        // 没有大于等于自己的就新建一个序列
        if(k >= cnt) cnt ++;
    }
    cout << cnt << endl;
    return 0;
}

参考代码二：二分优化

由于维护的数组具有单调性，可以直接二分去找！

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int w[N], f[N], g[N], n;

int main(){
    while(cin >> w[n]) n ++;

    // 最长不上升子序列
    int res = 0;
    for(int i = 0; i < n; i ++){
        f[i] = 1;
        for(int j = 0; j < i; j ++)
            if(w[j] >= w[i]) 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 l = 0, r = cnt;
        // g[]单调递增，通过二分找到小于w[i]的最大的数的位置
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(g[mid] < w[i]) l = mid;
            else r = mid - 1;
        }
        g[r + 1] = w[i];
        if(r + 1 > cnt) cnt ++;
    }
    cout << cnt << endl;
    return 0;
}

有个问题：为啥二分找第一个大于等于目标数的位置结果就不对呢？

如果有小伙伴发现了问题，欢迎留言！

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int w[N], f[N], g[N], n;

int main(){
    while(cin >> w[n]) n ++;

    // 最长不上升子序列
    int res = 0;
    for(int i = 0; i < n; i ++){
        f[i] = 1;
        for(int j = 0; j < i; j ++)
            if(w[j] >= w[i]) 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 l = 0, r = cnt;
        // g[]单调递增，通过二分找到第一个大于等于w[i]的位置
        while(l < r){
            int mid = l + r >> 1;
            if(g[mid] >= w[i]) r = mid;
            else l = r + 1;
        }
        g[r] = w[i];
        if(r >= cnt) cnt ++;
    }
    cout << cnt << endl;
    return 0;
}