你好！我是你的OI教练。

这道【导弹拦截】是NOIP历史上的一道里程碑式的题目，它完美地将最长不上升子序列和最长上升子序列这两个经典问题融合在了一起。正解需要使用 $O(N \log N)$ 的贪心+二分算法。

下面是符合 NOIP C++14 竞赛标准的题解代码。我在两个问题的解法中都加上了详细的注释，以阐明其贪心思想和实现细节。

核心思路回顾

1. 第一问：最多能拦截多少导弹？

   • 问题模型：求序列的最长不上升子序列 (LNIS)。
   • $O(N \log N)$ 解法：维护一个 tails 数组，tails[i] 表示长度为 i+1 的不上升子序列的最大结尾值。对于每个新来的导弹 x，在 tails 中找到第一个小于 x 的数并替换它。如果找不到（即 x 比 tails 中所有数都小或等于），则说明可以构成一个更长的不上升子序列，将 x 加入 tails 末尾。

2. 第二问：最少需要多少套系统？

   • 问题模型：根据 Dilworth 定理，等价于求序列的最长上升子序列 (LIS)。
   • $O(N \log N)$ 解法：维护一个 ends 数组，ends[i] 表示长度为 i+1 的上升子序列的最小结尾值。对于每个新来的导弹 x，在 ends 中找到第一个不小于 x 的数并替换它。如果找不到（即 x 比 ends 中所有数都大），则说明可以构成一个更长的上升子序列，将 x 加入 ends 末尾。

标准题解代码 (C++14)

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator> // 用于 std::istream_iterator

using namespace std;

// 解决第一问：最长不上升子序列 (LNIS)
int solve_lnis(const vector<int>& a) {
    if (a.empty()) {
        return 0;
    }

    // `tails` 数组。tails[i] 存储长度为 i+1 的不上升子序列的【最大】结尾值。
    // 结尾值越大，未来能接的数就越多，所以我们希望它尽可能大。
    // 这个数组在维护过程中是【单调不增】的（从大到小）。
    vector<int> tails;
    tails.push_back(a[0]);

    for (size_t i = 1; i < a.size(); i++) {
        int current_missile = a[i];

        // 情况1：如果当前导弹不高于 tails 的最后一个元素，
        // 说明它可以接在最长的不上升子序列后面，使其变得更长。
        if (current_missile <= tails.back()) {
            tails.push_back(current_missile);
        }
        // 情况2：当前导弹比 tails 的某个结尾要高。
        // 我们要用它来更新一个已有的子序列，让其结尾变得更大（更有潜力）。
        // 我们要找的是 tails 中第一个【严格小于】current_missile 的元素，并替换它。
        // 这相当于在一个从大到小的序列中，找第一个比 current_missile 小的位置。
        else {
            // `upper_bound` 在一个【升序】序列中查找第一个【大于】给定值的元素。
            // 我们的 tails 是【降序】的，所以需要使用反向迭代器或自定义比较器。
            // 这里使用 `upper_bound` 配合 `greater<int>()`，
            // 可以在降序序列中找到第一个【不大于】给定值的元素的位置。
            // 实际上，我们是要找第一个小于的，upper_bound 正好适用。
            auto it = upper_bound(tails.begin(), tails.end(), current_missile, greater<int>());
            *it = current_missile;
        }
    }

    return tails.size();
}

// 解决第二问：最长上升子序列 (LIS)
int solve_lis(const vector<int>& a) {
    if (a.empty()) {
        return 0;
    }
    
    // `ends` 数组。ends[i] 存储长度为 i+1 的上升子序列的【最小】结尾值。
    // 结尾值越小，未来能接的数就越多，所以我们希望它尽可能小。
    // 这个数组在维护过程中是【单调递增】的。
    vector<int> ends;
    ends.push_back(a[0]);

    for (size_t i = 1; i < a.size(); i++) {
        int current_missile = a[i];

        // 情况1：如果当前导弹高于 ends 的最后一个元素，
        // 说明它可以接在最长的上升子序列后面，使其变得更长。
        if (current_missile > ends.back()) {
            ends.push_back(current_missile);
        }
        // 情况2：当前导弹无法延长最长的上升子序列。
        // 我们要用它来更新一个已有的子序列，让其结尾变得更小（更有潜力）。
        // 我们要找的是 ends 中第一个【不小于】(>=) current_missile 的元素，并替换它。
        else {
            // `lower_bound` 在一个【升序】序列中查找第一个【不小于】给定值的元素。
            // 这正是我们需要的。
            auto it = lower_bound(ends.begin(), ends.end(), current_missile);
            *it = current_missile;
        }
    }

    return ends.size();
}

int main() {
    // 竞赛标准 IO 优化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // 技巧：处理单行未知数量的整数输入
    // istream_iterator 可以方便地从输入流中读取数据直到结束
    vector<int> missiles;
    int height;
    while(cin >> height){
        missiles.push_back(height);
    }

    // 计算并输出第一问的答案
    cout << solve_lnis(missiles) << endl;

    // 计算并输出第二问的答案
    cout << solve_lis(missiles) << endl;

    return 0;
}

👨‍🏫 教练划重点（关键点与易错点）

1. 第一问 LNIS 的二分查找：

   • 易错等级：⭐⭐⭐⭐⭐
   • 我们的 tails 数组是单调不增（降序）的。
   • 标准库的 lower_bound / upper_bound 默认用于单调递增（升序）序列。
   • 要在降序序列上使用它们，有两种方法：
     • 方法A (推荐)：使用 std::upper_bound 并传入一个自定义比较器 std::greater<int>()。upper_bound 在升序中找 >，配合 greater 就变成了在降序中找 <。这正是我们需要的。
     • 方法B：自己手写二分查找。这是最稳妥但代码稍长的方式。

2. 不上升 vs 下降，不下降 vs 上升：

   • 易错等级：⭐⭐⭐
   • 第一问是“不高于”，即 a[i] <= a[j]，所以是不上升。
   • Dilworth 定理对应的是上升，即 a[i] < a[j]。
   • 在写代码时，<= 和 <，>= 和 > 的区别要非常清楚。
     • LIS 贪心法用 lower_bound (>=)，因为相等的元素无法延长上升序列，但可以优化结尾。
     • LNIS 贪心法用 upper_bound (在降序中找 <)。

3. 输入处理：

   • 题目只说“一行，若干个整数”，没有给出具体数量。
   • 代码中使用了 while(cin >> height) 的循环来读取，直到输入流结束（遇到文件结尾 EOF 或非法输入）。这是处理此类不定长输入的标准方法。

4. 理解 $O(N \log N)$ 算法的本质：

   • 一定要记住，tails 和 ends 数组里存的不是一个真正的最长子序列，而是在每种长度下“最优潜力”的结尾值。
   • 这两个数组的长度，才是我们要求的答案。

这道题是 DP 优化的分水岭。请务必亲手把两种 $O(N \log N)$ 的解法都敲一遍并深刻理解，这对你后续学习更高级的算法大有裨益。

你好！我是你的OI教练。这道【导弹拦截】是NOIP历史上非常非常经典的一道题，它巧妙地将两个看似不同的问题包装在了一起，而这两个问题的解法又惊人地相似。

这道题是学习动态规划（DP），特别是**最长子序列（LIS）**问题从 $O(N^2)$ 到 $O(N\log N)$ 优化的必经之路。

我们一步一步来分析，拿出你的草稿纸，跟我一起推导。

第一部分：思路提示

这道题有两个问题，我们要分开思考。

第一问：一套系统最多能拦截多少导弹？

• 规则：“以后每一发炮弹都不能高于前一发的高度”。
• 翻译：假设导弹依次来的高度是序列 $A = \{a_1, a_2, \ldots, a_n\}$。我们要从中按顺序挑出一部分导弹，形成一个新的子序列 $B = \{b_1, b_2, \ldots, b_k\}$，这个子序列必须满足 $b_1 \ge b_2 \ge \ldots \ge b_k$。
• 目标：让这个子序列 $B$ 的长度 $k$ 尽可能大。
• 结论：这个问题就是在求原序列 $A$ 的最长不上升子序列 (Longest Non-Increasing Subsequence, LNIS) 的长度。

第二问：拦截所有导弹最少要配备多少套系统？

• 规则：每套系统都遵循第一问的规则（不上升）。
• 目标：用最少的系统（最少的不上升子序列），把所有导弹都覆盖掉。
• 贪心思考：当一个新的导弹 $a_i$ 飞来时，我们应该让哪个已经存在的系统去拦截它？
  • 选项1：启动一套新系统。
  • 选项2：交给一个旧系统。
  • 为了让系统总数最少，我们肯定优先选2。
  • 在所有能拦截 $a_i$ 的旧系统中（即上一发导弹高度 $\ge a_i$），我们应该选哪一个？
    • 思考：如果我用一个上一发很高（比如800）的系统去拦截一个很低（比如100）的导弹，那这个系统以后就只能拦截 $\le 100$ 的了，非常“浪费”。
    • 如果我用一个上一发刚好（比如120）的系统去拦截100，那这个系统变得更受限，但影响不大。
  • 贪心策略：对于每个新来的导弹，我们应该在所有能拦截它的系统中，找到那个**“最勉强”的系统来拦截。也就是，找到一个系统，它的上一发炮弹高度 $h$ 满足 $h \ge a_i$，并且 $h$ 在所有满足条件的系统中是最小**的。
• 神奇的结论：这个贪心策略，最终会发现，我们需要的系统数，恰好等于原序列的最长上升子序列 (Longest Increasing Subsequence, LIS) 的长度。
  • 这背后是著名的数学定理 Dilworth定理，它的一个特例是：“一个序列的最少不上升子序列划分数等于其最长上升子序列的长度”。

第二部分：预备知识点总结

1. 动态规划基础：理解状态和转移。
2. 最长上升/不上升子序列：
   • $O(N^2)$ 算法：dp[i] 表示以第 i 个元素结尾的最长子序列长度。dp[i] = 1 + max(dp[j])，其中 j<i 且 a[j] 满足条件。这能通过50%的数据。
   • $O(N\log N)$ 算法：贪心 + 二分查找。这是通过本题100%数据的核心。你需要非常熟悉这个算法。
3. Dilworth定理 (选修)：了解这个定理能让你更深刻地理解第二问的本质，但即使不知道，也能通过贪心直觉做出。

第三部分：启发式教学 —— 草稿纸上的推演

我们来重点推演 $O(N\log N)$ 的解法，因为它能同时解决两个问题。

样例数据：389 207 155 300 299 170 158 65

第一问：最长不上升子序列 (LNIS)

我们维护一个数组 tails，tails[k] 存储的是长度为 k+1 的不上升子序列的“最优”结尾。这里的“最优”指的是结尾值尽可能大，因为结尾越大，将来能接的数就越多。

1. 处理 389：tails 为空，389 自己构成长度为1的序列。 tails = [389]
2. 处理 207：207 <= 389，可以接在后面，形成更长的序列。 tails = [389, 207]
3. 处理 155：155 <= 207，可以接在后面。 tails = [389, 207, 155]
4. 处理 300：300 > 155，不能接在后面。它应该去更新 tails 里的某个值，让结尾更有潜力。
   • 它应该替换掉 tails 中第一个比它小的数。upper_bound 查找第一个小于300的数（在从大到小的序列中）。
   • 389 > 300, 207 < 300。所以 300 替换 207。
   • tails = [389, 300, 155]。 这表示我们现在有长度为2的序列（结尾是300）和长度为3的序列（结尾是155），而长度为2的这个新序列比以前那个结尾是207的更有潜力。
5. 处理 299：299 > 155。替换掉 tails 中第一个比它小的数 155。tails = [389, 300, 299]
6. 处理 170：170 <= 299，可以接在后面。 tails = [389, 300, 299, 170]
7. 处理 158：158 <= 170，可以接在后面。 tails = [389, 300, 299, 170, 158]
8. 处理 65：65 <= 158，可以接在后面。 tails = [389, 300, 299, 170, 158, 65]

最终 tails 的长度为 6，所以第一问答案是 6。

• 代码提示：STL中的 upper_bound 配合自定义比较器 greater<int>() 可以帮你找到那个要替换的位置。

第二问：最长上升子序列 (LIS)

这个就是标准的 LIS 模板了。我们维护一个数组 ends，ends[k] 存储长度为 k+1 的上升子序列的最小结尾。

1. 处理 389：ends 为空，389 自己构成长度为1的序列。 ends = [389]
2. 处理 207：207 < 389。它不能构成更长的序列，但它可以优化已有的序列。它比 389 更有潜力。
   • 找到 ends 中第一个不小于 207 的数（lower_bound），也就是 389，用 207 替换它。
   • ends = [207]。这表示我们找到了一个长度为1的，结尾更小的序列。
3. 处理 155：155 < 207，同理，替换。 ends = [155]
4. 处理 300：300 > 155，可以接在后面，形成更长的序列。ends = [155, 300]
5. 处理 299：299 < 300。找到第一个不小于 299 的数 300，替换。ends = [155, 299]
6. 处理 170：170 > 155。找到第一个不小于 170 的数 299，替换。ends = [155, 170]
7. 处理 158：158 > 155。找到第一个不小于 158 的数 170，替换。ends = [155, 158]
8. 处理 65：65 < 155。找到第一个不小于 65 的数 155，替换。 ends = [65, 158]

最终 ends 的长度为 2，所以第二问答案是 2。

第四部分：理解题意的关键词

• “依次飞来”：暗示了顺序是固定的，我们不能重新排列导弹，必须处理子序列，而不是子集。
• “不能高于前一发”：这是定义核心规则的句子，直接翻译为“不上升”（>=），而不是“下降” (>)。这是第一问的关键。
• “最多能拦截多少”：暗示求最长 (Longest) 子序列。
• “最少要配备多少套”：暗示这是一个最小覆盖/划分 (Minimum Partition) 问题，这是第二问的关键，可以联想到贪心或者更深层的定理。