之前的我怎么这么菜。
看到这题还没 A 直接原地红温，被硬控了半分钟。

第一问做一个最长不上升子序列 DP 就好了。
第二问考虑最小链覆盖等于最长反链，所以做一个最长上升子序列 DP 就好了。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15;
int n, a[N];
int f[N], g[N];
int main() {
    while (~scanf("%d", &a[++n]));
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++) {
            if (a[j] >= a[i]) f[i] = max(f[i], f[j] + 1);
            else g[i] = max(g[i], g[j] + 1);
        }
    int ans1 = 0, ans2 = 0;
    for (int i = 1; i <= n; i++) ans1 = max(ans1, f[i]), ans2 = max(ans2, g[i]);
    printf("%d\n%d\n", ans1, ans2);
    return 0;
}

这样是 $O(n^2)$ 的，然后直接怒拍了一个线段树板子把它 C 过去了。

虽然树状数组也可以。
另外提一嘴这玩意儿可以离散化。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15, M = 5e4 + 15;
int n, a[N], Max = 0;
int f[N], g[N];

struct qwq {
    struct Tree {
        int l, r;
        int Max;
    } tr[M << 2];
    void pushup(int u) {
        tr[u].Max = max(tr[u << 1].Max, tr[u << 1 | 1].Max);
    }
    void build(int u, int l, int r) {
        tr[u].l = l, tr[u].r = r;
        tr[u].Max = 0;
        if (l == r) return;
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }
    void change(int u, int x, int d) {
        if (tr[u].l == tr[u].r) {
            tr[u].Max = max(tr[u].Max, d);
            return;
        }
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) change(u << 1, x, d);
        else change(u << 1 | 1, x, d);
        pushup(u);
    }
    int query(int u, int l, int r) {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].Max;
        int mid = tr[u].l + tr[u].r >> 1;
        int res = 0;
        if (l <= mid) res = max(res, query(u << 1, l, r));
        if (r > mid) res = max(res, query(u << 1 | 1, l, r));
        return res;
    }
} t1, t2;

int main() {
    while (~scanf("%d", &a[++n]));
    for (int i = 1; i <= n; i++) Max = max(Max, a[i]);
    n--;
    t1.build(1, 0, Max), t2.build(1, 0, Max);
    for (int i = 1; i <= n; i++) {
        f[i] = t1.query(1, a[i], Max) + 1;
        g[i] = t2.query(1, 0, a[i] - 1) + 1;
        t1.change(1, a[i], f[i]);
        t2.change(1, a[i], g[i]);
    }
    int ans1 = 0, ans2 = 0;
    for (int i = 1; i <= n; i++) ans1 = max(ans1, f[i]), ans2 = max(ans2, g[i]);
    printf("%d\n%d\n", ans1, ans2);
    return 0;
}