1999年NOIP提高组导弹拦截（洛谷P1020）：从暴力到最优解

2天前比赛题解53

1999年的NOIP经典题目“导弹拦截”是NOIP竞赛中的经典动态规划问题，考察选手对最长子序列算法的理解和应用。本文将详细解析题目要求，并逐步讲解O(nlogn)的最优解法。

一、题目分析

题目要求解决两个问题：

一套系统最多能拦截多少导弹（最长不上升子序列）
拦截所有导弹最少需要多少套系统（最长上升子序列）

二、完整代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespACe std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);  // 优化输入输出速度
    
    vector<int> missiles;
    int height;
    
    // 高效读取输入数据
    while (cin >> height) {
        missiles.push_back(height);
    }
    
    int n = missiles.size();
    
    // 第一问：O(nlogn)求最长不上升子序列
    vector<int> dp;
    for (int h : missiles) {
        // 使用upper_bound在降序序列中查找插入位置
        auto it = upper_bound(dp.begin(), dp.end(), h, greater<int>());
        if (it == dp.end()) {
            dp.push_back(h);  // 当前导弹高度小于所有序列末尾，新建序列
        } else {
            *it = h;  // 替换第一个小于等于当前高度的位置
        }
    }
    int max_intercept = dp.size();  // dp数组长度即为最长不上升子序列长度
    
    // 第二问：O(nlogn)求最长上升子序列
    vector<int> tails;
    for (int h : missiles) {
        // 使用lower_bound在升序序列中查找插入位置
        auto it = lower_bound(tails.begin(), tails.end(), h);
        if (it == tails.end()) {
            tails.push_back(h);  // 当前导弹高度大于所有序列末尾，新建序列
        } else {
            *it = h;  // 替换第一个大于等于当前高度的位置
        }
    }
    int system_count = tails.size();  // tails数组长度即为最少系统数
    
    cout << max_intercept << "\n" << system_count << "\n";
    return 0;
}