Dilworth 定理

狄尔沃斯定理（Dilworth’s theorem）亦称偏序集分解定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真，它断言：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目

该定理在子序列问题上可表述为：把序列分成不升子序列的最少个数，等于序列的最长上升子序列长度。把序列分成不降子序列的最少个数，等于序列的最长下降子序列长度

该定理在二分图上等价于柯尼希定理：二分图最小点覆盖的点数等于最大匹配数

定理法

给定正整数序列，求最长不升子序列长度，以及能覆盖整个序列的不升子序列的最少个数 （对应题目，[NOIP 1999 提高组] 导弹拦截 https://www.luogu.com.cn/problem/P1020）

问题一套用 LIS 模型即可求解。由 Dilworth 定理

问题二等价于 LIS 长度

#include <cstdio>

#define max(a, b) ((a) > (b) ? (a) : (b))
#define rep(i, s, e) for (int i = s; i <= e; i ++)
#define N 1010

int a[N], f[N], g[N];

int main() {
    int n = 1; while (~scanf("%d", a + n)) n ++; n --;

    rep(i, 1, n) rep(j, 0, i - 1) {
        bool down = a[j] >= a[i];
        f[i] = max(f[i], down * f[j] + 1);
        g[i] = max(g[i], !down * g[j] + 1);
    }

    int r1 = 0, r2 = 0;
    rep(i, 1, n) r1 = max(r1, f[i]), r2 = max(r2, g[i]);

    printf("%d\n%d\n", r1, r2);

    return 0;
}

贪心法

对于每个数，既可以把它接到已有子序列后面，也可以建立一个新序列。要使子序列数最少，应尽量不建立新序列。此外，应让每个子序列的末尾尽可能大，这样能接的数更多。因为一个数若能接到小数后面，必然能接到大数后面，反之则不成立。根据这些想法，可总结出如下贪心流程：

从前往后扫描每个数，对于当前数

若现有子序列的结尾都小于它，则创建新子序列 否则，将它放到结尾大于等于它的最小数后面 证明

记 A 为贪心解，B 为最优解

贪心解能覆盖所有数，且形成的都是不升序列，因此合法。由定义，B≤A 假设最优解对应的方案和贪心方案不同，从前往后找到第一个不在同一序列的数 x。假设贪心解中 x 前面的数是 a，最优解中 x 前面的数是 b，a 后面的数是 y，由于贪心会让当前数接到大于等于它的最小数后面，所以 x,y≤a≤b,。此时，在最优解中，把 x 一直到序列末尾，和 y 一直到序列末尾交换位置，这样做不影响正确性，也不增加序列个数，但会使 x 在最优解和贪心解中所处的位置相同。由于序列中的数是有限的，只要一直做下去，一定能使最优解变为贪心解。因此 A≤B综上 A=B实现用 g 保存每条不升子序列的末尾，可用归纳法证明 g 是单调上升的。初始时，g 为空满足条件。假设 g 已经单调上升，现在要加入数 x，设 g[i] 是大于等于 x 的最小数，则 g[i−1]

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com