题目链接：https://www.luogu.com.cn/problem/P1020

题目大意：

给你一串数，求：

1. 这串数的最长不上升子序列的长度；
2. 最少划分成多少个子序列是的这些子序列都是不上升子序列。

第一个问题比较简单，就是用二分的方法 O(log n) 可以解决这个问题。

第二个问题，可以用 Dilworth定理 证明：

在一个序列中，最长不上升子序列的最少划分数就等于其最长上升子序列的长度

Dilworth定理参考自：https://www.cnblogs.com/ZDHYXZ/p/6871802.html

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;

int n, cnt, a[maxn], h[maxn], ans;

int main() {

    while (~scanf("%d", &a[n])) n ++;

    for (int i = 0; i < n; i ++) {

        int id = upper_bound(h, h+cnt, a[i], greater<int>()) - h;

        if (id == cnt) h[cnt++] = a[i];

        else h[id] = a[i];

    }

    ans = cnt;

    cnt = 0;

    for (int i = 0; i < n; i ++) {

        int id = lower_bound(h, h+cnt, a[i]) - h;

        if (id == cnt) h[cnt++] = a[i];

        else h[id] = a[i];

    }

    printf("%d\n%d\n", ans, cnt);

    return 0;

}