[NOIP 1999 提高组] 导弹拦截

题意

给出一串导弹高度。

一套拦截系统可以拦截一个不上升序列，也就是后一次拦截的高度不能高于前一次。

要求输出：

一套系统最多能拦截多少枚导弹；
要拦截全部导弹，最少需要多少套系统。

思路

先看一个 $O(n^2)$ 的 DP：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44// brute.cpp：小数据朴素解，用 O(n^2) DP 分别求最长不上升和最长上升子序列。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;

int n;
int a[MAXN];
int dp1[MAXN], dp2[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while (cin >> a[n + 1]) {
        n++;
    }

    int ans1 = 0;
    for (int i = 1; i <= n; i++) {
        dp1[i] = 1;
        for (int j = 1; j < i; j++) {
            if (a[j] >= a[i]) {
                dp1[i] = max(dp1[i], dp1[j] + 1);
            }
        }
        ans1 = max(ans1, dp1[i]);
    }

    int ans2 = 0;
    for (int i = 1; i <= n; i++) {
        dp2[i] = 1;
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i]) {
                dp2[i] = max(dp2[i], dp2[j] + 1);
            }
        }
        ans2 = max(ans2, dp2[i]);
    }

    cout << ans1 << '\n';
    cout << ans2 << '\n';
    return 0;
}

第一问很直接：求最长不上升子序列。设 dp[i] 表示以第 i 枚导弹结尾时，最多能接住多少枚，若 a[j] >= a[i]，就能从 j 转移到 i。

第二问要用一个经典结论：把整个序列划分成尽量少的不上升子序列，答案等于最长上升子序列长度。直观理解是，如果存在一个严格上升子序列，那么这些导弹两两不能放在同一套不上升系统里，所以至少需要这么多套；贪心分配也能达到这个数量。

正式代码用二分维护尾值，把两问都优化到 $O(n log n)$ ：

第一问：对 -a[i] 求最长不下降子序列；
第二问：对 a[i] 求最长严格上升子序列。

为什么第一问用 -a[i]？因为原序列里的不上升：

text

1a[j] >= a[i]

等价于取负后的不下降：

text

1-a[j] <= -a[i]

DP 公式

第一问：最长不上升子序列。设 $dp_i$ 表示以第 $i$ 枚导弹结尾时最多能拦截的导弹数。初始化 $dp_i = 1$ ，转移为：

dp_i = \max_{j < i,\ a_j \geqslant a_i}(dp_j + 1)

答案为 $\max_i dp_i$ 。用二分维护尾值可优化到 $O(n \log n)$ ：对 $-a_i$ 求最长不下降子序列。

第二问：由 Dilworth 定理，最少不上升子序列覆盖数等于最长严格上升子序列长度。设 $f_i$ 表示以第 $i$ 枚导弹结尾的最长严格上升子序列长度：

f_i = \max_{j < i,\ a_j < a_i}(f_j + 1)

答案为 $\max_i f_i$ 。用二分维护尾值可优化到 $O(n \log n)$ 。

样例 DP 表格

以样例 389 207 155 300 299 170 158 65 为例，展示 $O(n^2)$ DP 的逐位置计算过程：

$i$	$a_i$	$dp_i$ （第一问：不上升）	转移来源	$f_i$ （第二问：严格上升）	转移来源
1	389	1	—	1	—
2	207	2	$dp_1+1$ （389≥207）	1	—
3	155	3	$dp_2+1$ （207≥155）	1	—
4	300	2	$dp_1+1$ （389≥300）	2	$f_2+1$ （207<300）
5	299	3	$dp_4+1$ （300≥299）	2	$f_3+1$ （155<299）
6	170	4	$dp_5+1$ （299≥170）	2	$f_3+1$ （155<170）
7	158	5	$dp_6+1$ （170≥158）	2	$f_3+1$ （155<158）
8	65	6	$dp_7+1$ （158≥65）	1	—

第一问答案： $\max(dp) = 6$ ，对应不上升子序列 389, 300, 299, 170, 158, 65。第二问答案： $\max(f) = 2$ ，对应严格上升子序列如 155, 300。由 Dilworth 定理，至少需要 2 套系统。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;

int n;
int a[MAXN]; // 导弹高度序列

int longest_non_increasing() {
    vector<int> tail;
    for (int i = 1; i <= n; i++) {
        int x = -a[i];
        vector<int>::iterator it = upper_bound(tail.begin(), tail.end(), x);
        if (it == tail.end()) {
            tail.push_back(x);
        } else {
            *it = x;
        }
    }
    return (int)tail.size();
}

int longest_increasing() {
    vector<int> tail;
    for (int i = 1; i <= n; i++) {
        int x = a[i];
        vector<int>::iterator it = lower_bound(tail.begin(), tail.end(), x);
        if (it == tail.end()) {
            tail.push_back(x);
        } else {
            *it = x;
        }
    }
    return (int)tail.size();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while (cin >> a[n + 1]) {
        n++;
    }

    cout << longest_non_increasing() << '\n';
    cout << longest_increasing() << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n log n)$
空间复杂度： $O(n)$

总结

本题两问分别对应：

最长不上升子序列；
最少不上升序列覆盖数，也就是最长上升子序列。

把这两个模型分清，代码就只剩二分维护尾值。