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

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

2个月前 (06-18)

1999年NOIP提高组导弹拦截(洛谷P1020)解题思路与动态规划代码解析  动态规划 最长上升子序列 最长下降子序列 NOIP提高组 第1张

一、题目解读

    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;
}

五、总结

    本解法巧妙将导弹拦截问题转化为经典动态规划模型(LIS/LDS),并通过二分查找函数大幅优化效率。代码简洁且逻辑清晰,体现了“问题转化”与“算法优化”在竞赛编程中的重要性。掌握此类技巧,能有效应对涉及序列极值统计的复杂场景。



原创内容 转载请注明出处

分享给朋友:

相关文章

力扣1137题:动态规划解泰波那契数 高效求解第N项的秘密

力扣1137题:动态规划解泰波那契数 高效求解第N项的秘密

一:重新解读题目泰波那契数列是一个充满数学趣味的递推序列:从第3项开始,每个数均为前三个数的和(即Tₙ₊₃ = Tₙ + Tₙ₊₁ + Tₙ₊₂)。当给定整数n时,需要高效计算出第n项的值。面对此类递...

CSP-J 2019纪念品题解(洛谷P5662):动态规划+完全背包问题的实战应用

CSP-J 2019纪念品题解(洛谷P5662):动态规划+完全背包问题的实战应用

一、题目解读2019年CSP-J的“纪念品”问题(对应洛谷P5662)要求玩家在T天内通过买卖纪念品最大化金币收益。每天可交易N种商品,需计算最优策略下的最终金币数。题目强调动态规划思维与资源分配优化...

NOIP 2008火柴棒等式题解(C++代码实现)  动态规划与枚举算法详解

NOIP 2008火柴棒等式题解(C++代码实现) 动态规划与枚举算法详解

一、题目解读火柴棒等式问题(NOIP 2008,洛谷P1149)要求使用给定数量的火柴棒,构造形如 A + B = C 的等式,其中A、B、C均为整数,且火柴棒总数恰好等于输入值。需统计符合条件的等式...

CSP-J 2019公交换乘题解析:基于队列优化的动态规划代码详解

CSP-J 2019公交换乘题解析:基于队列优化的动态规划代码详解

一、题目解读CSP-J 2019年的“公交换乘”题目(洛谷P5661)要求模拟地铁与公交交替出行的费用计算。题目核心在于地铁消费会产生优惠券,而公交可在45分钟内使用优惠券抵扣车费。需要处理n条出行记...

力扣931题最小下降路径和解析 动态规划解法 LeetCode解题技巧

力扣931题最小下降路径和解析 动态规划解法 LeetCode解题技巧

一、题目解读力扣931题「Minimum Falling Path Sum」(最小下降路径和)要求在一个n x n的整数矩阵中,计算从顶部到底部的最小路径和。路径只能从每个位置向下或对角线移动(即向下...

牛客25461题解析:花园喷泉距离优化算法(动态规划+后缀数组解法)

牛客25461题解析:花园喷泉距离优化算法(动态规划+后缀数组解法)

一、题目解读牛客25461题要求计算一个花园中n朵花到两个喷泉的最小距离平方和。用户需输入喷泉坐标(x1,y1)和(x2,y2),以及n朵花的坐标(x,y),通过合理分配每朵花到两个喷泉的距离,使总距...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。