P4794 导弹攻防战（提高）

解题思路

1. 读懂题目：一套导弹拦截系统，拦截的第一发炮弹可以是任意高度，但之后每一发的高度都不能高于前一发（也就是高度只能一路下降或持平）。导弹按固定顺序来袭，问最少需要几套系统才能把所有导弹全部拦截。

2. 重要结论：最少需要的系统套数 = 导弹高度序列中"最长严格上升子序列"的长度。

3. 为什么是这个结论：一套系统内的导弹高度是"一路往下"的（非递增）。如果有一些导弹的高度是严格上升的，比如 207、300、310，那么它们不可能放进同一套系统——因为后一发必须不高于前一发，上升就违反规则了。所以至少需要"最长严格上升子序列长度"那么多套系统。而用贪心安排，正好能做到这么多套，不多不少。这就是著名的 Dilworth 定理思想。

4. 怎么求最长严格上升子序列：用动态规划。设 dp[i] 表示"以第 i 枚导弹结尾"的最长严格上升子序列的长度。初始化时 dp[i]=1，表示序列里只有这一枚导弹自己。然后对每一枚导弹 i，回头检查它前面的每一枚导弹 j：如果 missile[j]<missile[i]，说明第 i 枚可以接在第 j 枚后面，dp[i] 就可以更新为 dp[j]+1（取较大值）。最后答案就是所有 dp[i] 里最大的那个。

5. 看例子：样例导弹高度 389,207,300,200,310,65。其中 207、300、310 是严格上升的，长度是 3，所以最少需要 3 套系统。一种可行安排：系统 1 拦 389,207,200,65；系统 2 拦 300；系统 3 拦 310。

6. 注意"严格"两个字：如果导弹高度相等，比如 5,5,5，一套系统就能全拦住（后一发不高于前一发，5 不高于 5），此时最长严格上升子序列长度是 1，答案就是 1。所以判断条件是 missile[j]<missile[i]，不能写成小于等于。

7. 边界情况：n=1 时只有一枚导弹，答案就是 1；n≤500，每枚导弹高度不超过 30000，O(n²) 的动态规划完全够用。

参考代码

// P4794 导弹攻防战：最少系统数 = 最长严格上升子序列的长度（经典结论）
#include <iostream>
using namespace std;
int missile[505];  // 导弹的高度
int dp[505];       // dp[i]：以第 i 枚导弹结尾的最长严格上升子序列长度

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> missile[i];
    int answer = 0;  // 最少需要的拦截系统套数
    for (int i = 0; i < n; i++) {
        dp[i] = 1;   // 只有这一枚导弹自己
        // 枚举前面的导弹，尝试接在后面构成上升子序列
        for (int j = 0; j < i; j++) {
            if (missile[j] < missile[i] && dp[j] + 1 > dp[i])
                dp[i] = dp[j] + 1;
        }
        if (dp[i] > answer) answer = dp[i];
    }
    cout << answer << endl;
    return 0;
}

复杂度分析

动态规划有两层循环：外层枚举每一枚导弹，内层枚举它前面的所有导弹，时间是 O(n²)。n≤500，最多 25 万次运算，非常快。空间上用了两个长度为 505 的数组，是 O(n)。这是一道经典的"最长上升子序列"问题，掌握后很多题都能用。