题目简化 给定一个数列 b，问：

它的最长不上升子序列长度； 最少能被划分成多少个不上升子序列。 思路讲解 一、为什么要求 最长不上升子序列： 但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

rt，因为每一个系统的第 i 发高度都不能高于第 i−1 发的高度，则该数列为 不上升子序列。

二、为什么要求 最长上升子序列： Dilworth 定理 对偏序集 ⟨A,≤⟩，设 A 中最长链的长度是 n，则将 A 中元素分成不相交的反链，反链个数至少是 n。

名词解释：

偏序关系：对于集合 A 上的二元关系 R，若 R 具有自反性，反对称性，传递性，那么 R 称为 A 的偏序关系，一般记作 ≤（注意这里的 ≤ 不必是指一般算数意义上的“小于等于”。）。

偏序集：若在集合 A 上给定一个偏序关系 ≤，则称集合 A 按偏序关系 ≤ 构成一个偏序集合，集合 A 和偏序 R 一起称为偏序集，记作 ⟨A,≤⟩。

反链：对于偏序集合 ⟨A⟩，在 ⟨A⟩ 的一个子集中，如果每两个元素都是无关的，则称这个子集为反链。

综上可简化为：最少的不上升子序列的个数就是最长上升子序列的长度。

偏序集 ⟨A,≤⟩ 是指数列 b。 所以得出结论：导弹系统最少套数就是最长上升子序列的长度。

代码实现 一、求最长不上升子序列： 用普通的方法是不可以的，那个的时间复杂度是 O(n 2 )。 所以需要用到 stl 函数：lower_bound 与 upper_bound。 对这个不熟悉的同学可以看 oiwiki STL 算法部分。

变量声明： 数组 b 存储从输入数据； 数组 l 存储最长不上升子序列； 变量 r1 代表 l 的结尾位置（即最长不上升子序列的长度）。

把 b 中的每个元素挨个放到 l 里：

如果 b i ​ ≤l r1 ​ ，说明 b i ​ 可以直接加入 l（而整个 l 数组还是有序的）；

如果 b i ​

l r1 ​ ，说明若放入 b i ​ 则 l 会无序，所以要找办法把 b i ​ 放进去：

怎么放呢？在 l 中找到第一个小于 b i ​ 的数，用 b i ​ 代替它。 找到第一个小于 b i ​ 的数，使用 upper_bound 可以在 O(logn) 复杂度内找到（需要改比较器）。

由于它返回的是指针就可以有一些奇特操作。

*upper_bound(l+1, l+r1+1, b[i], greater()) = b[i];

证明： 更优性证明：

设找到的数为 l p ​ 。

如果 l p ​ 在末尾，由于 l p ​ <b i ​ ，所以 l p ​ 后面能接的没有 b i ​ 多，l p ​ 让位给 b i ​ 可以让序列更长。

如果 l p ​ 不在末尾，那 l p ​ 以后都不会再被用到了，直接换了 l p ​ 就行。

有序性证明：

设 l p ​ 前面是 p 1 ​ ，l p ​ 后面是 p 2 ​ ，则有

p 1 ​ ≤l p ​ ≤p 2 ​

因为 l p ​ 是第一个小于 b i ​ 的，所以有

b i ​ ≤p 2 ​

又因为

p 1 ​ ≤l p ​ ≤b i ​

所以

p 1 ​ ≤b i ​ ≤p 2 ​

综上，b i ​ 可以完美代替 l p ​ 。

实际上，l p ​ 的含义是：最大不上升子序列长度为 p 时，最优的结尾元素。 最后 r1 就是要求的最大不上升子序列长度。

二、求最长上升子序列长度 这里和上面很像，所以不用改比较器，而且因为是上升序列，所以要用 lower_bound。

基本上是“同上”二字就可以概括。

CODE

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int man = 1e5+10;

int n, r1, r2;
int a[man], l[man], h[man];
int main () {
#ifndef ONLINE_JUDGE 
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    while (scanf("%d", a+(++n)) != EOF) ; --n;
    l[1] = h[1] = a[1]; r1 = r2 = 1;
    for(int i = 2; i <= n; ++ i) {
        if (l[r1] >= a[i]) l[++r1] = a[i];
        else *upper_bound(l+1, l+r1+1, a[i], greater<int>()) = a[i];
        if (h[r2] < a[i]) h[++r2] = a[i];
        else *lower_bound(h+1, h+r2+1, a[i]) = a[i];
    } printf("%d\n%d", r1, r2);
    return 0;
}

扩展：Dilworth 定理的证明 施归纳于 n。

当 n=1 时： 命题显然成立。

假设对于 n=k 结论成立，考虑 n=k+1 的情况： 当 A 中最长链的长度为 k+1 时，令 M 为 A 中极大元的集合，显然 M 是一条反链。而且 A−M 中最长链的长度为 k。

由归纳假设，可以把 A−M 分成至少 k 个不相交的反链，加上反链 M，则 A 可分成至少 k+1 条反链。 因为 A 不可能分解成 n−1 条反链。假若只有 n−1 条反链，那么最长链的 n 个元素中必有 2 个元素被分到同一个反链，显然这与反链的定义矛盾。