题解 - P1020

STA_Morlin · 2022-06-20 17:33:50 · 题解

$\text{UPD 2023.09.05}$：修改文中语义不明处。

P1020 导弹拦截の题目传送门。

题目简化

给定一个数列 b，问：

它的最长不上升子序列长度；

最少能被划分成多少个不上升子序列。

思路讲解

一、为什么要求 最长不上升子序列：

但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

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

二、为什么要求 最长上升子序列：
Dilworth 定理

对偏序集 \langle A, \le \rangle，设 A 中最长链的长度是 n，则将 A 中元素分成不相交的反链，反链个数至少是 n。

名词解释：

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

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

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

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

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

代码实现

一、求最长不上升子序列：

用普通的方法是不可以的，那个的时间复杂度是 O(n^2)。
所以需要用到 stl 函数：lower_bound 与 upper_bound。
对这个不熟悉的同学可以看 oiwiki STL 算法部分。

变量声明：

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

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

如果 b_i \le 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(\log n) 复杂度内找到（需要改比较器）。

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

*upper_bound(l+1, l+r1+1, b[i], greater<int>()) = 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 \le l_p \le p_2

因为 l_p 是第一个小于 b_i 的，所以有

b_i \le p_2

又因为

p_1 \le l_p \le b_i

所以

p_1 \le b_i \le 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 个元素被分到同一个反链，显然这与反链的定义矛盾。