当前位置：首页 > 提高组 > 1999年NOIP提高组导弹拦截（洛谷P1020）解题思路与动态规划代码解析

1999年NOIP提高组导弹拦截（洛谷P1020）解题思路与动态规划代码解析

3个月前 (06-18)

一、题目解读

1999年NOIP提高组“导弹拦截”问题（对应洛谷P1020）要求设计导弹拦截系统：给定一组导弹高度数据，需计算最少拦截系统数量，并求最多能拦截的导弹数。核心难点在于将问题转化为最长不上升子序列（第一问）与最长上升子序列（第二问）的求解，考验动态规划与序列分析能力。

二、解题思路

采用动态规划+二分查找优化策略：

1. 第一问：最长不上升子序列（LDS）——维护一个存储当前最长LDS末尾元素的数组dp，通过upper_bound（从大到小查找第一个大于目标值的迭代器）动态更新，确保序列严格不上升。

2. 第二问：最长上升子序列（LIS）——类似思路，利用lower_bound（从小到大查找第一个大于等于目标值的迭代器）维护LIS末尾，得到拦截系统数量。

两者时间复杂度均为O(nlogn)，避免暴力枚举。

三、解题步骤

1. 数据输入：循环读入导弹高度，存入missiles向量。

2. LDS求解：遍历导弹高度，通过upper_bound在dp中查找可替换的末尾元素（若未找到则扩展序列），最终dp.size()即为拦截数。

3. LIS求解：同理用lower_bound更新tails数组，其大小即为所需系统数量。

4. 输出结果：两问答案分别对应LDS长度与LIS长度。

四、代码与注释

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加速IO

    vector<int> missiles; // 存储导弹高度
    int height;
    
    // 高效读取输入数据
    while (cin >> height) {
        missiles.push_back(height);
    }
    
    int n = missiles.size();
    
    // 第一问：O(nlogn)求最长不上升子序列
    vector<int> dp; // 存储LDS末尾元素
    for (int h : missiles) {
        auto it = upper_bound(dp.begin(), dp.end(), h, greater<int>()); // 从大到小查找第一个大于h的位置
        if (it == dp.end()) { // 若未找到，扩展序列
            dp.push_back(h);
        } else {
            *it = h; // 替换末尾元素（缩短序列长度）
        }
    }
    int max_intercept = dp.size(); // LDS长度即拦截数
    
    // 第二问：O(nlogn)求最长上升子序列
    vector<int> tails; // 存储LIS末尾元素
    for (int h : missiles) {
        auto it = lower_bound(tails.begin(), tails.end(), h); // 从小到大查找第一个大于等于h的位置
        if (it == tails.end()) {
            tails.push_back(h);
        } else {
            *it = h; // 替换末尾元素（优化序列长度）
        }
    }
    int system_count = tails.size(); // LIS长度即系统数量
    
    cout << max_intercept << "\n" << system_count << "\n";
    return 0;
}