每日一练 洛谷 P1020 [NOIP 1999 提高组] 导弹拦截

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行，若干个整数，中间由空格隔开。

输出格式

两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出样例

输入 #1

389 207 155 300 299 170 158 65

输出 #1

6
2

样例解释

• 最长非递增子序列：389, 300, 299, 170, 158, 65 或 389, 207, 155, 170, 158, 65 等，长度为 6。
• 至少需要 2 套系统才能拦截全部导弹，因为导弹高度变化趋势无法被单一非递增序列覆盖。

---

解题思路

本题是经典的动态规划 + 贪心优化问题，包含两个子问题：

问题一：求最长非递增子序列（LDS）

• 即在序列中找出一个最长的子序列，使得每个元素不大于前一个元素。
• 可通过将原序列取负，转化为求最长非递减子序列，或直接使用贪心+二分优化实现。

问题二：求最少非递增子序列划分数

• 根据Dilworth 定理：一个偏序集的最少链划分等于其最大反链的大小。
• 在本题中，“链”是非递增序列，“反链”是严格递增序列。
• 因此，最少非递增子序列划分数 = 最长严格递增子序列（LIS）的长度。

---

算法优化说明

直接使用 O(n2)O(n2) 的 DP 会超时（当数据量较大时），因此采用贪心 + 二分查找优化到 O(nlog⁡n)O(nlogn)。

• 使用数组 g[] 维护当前“候选序列”的尾部元素。
• 对于每个新元素，若能接在末尾则直接加入；否则替换第一个不满足条件的位置，保持序列有序性。

完整代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;  // 数组最大长度，足够处理大数据

int a[N], x, n;         // a[] 存储导弹高度，x 临时读入，n 为导弹总数
int dp[N], maxn;        // dp 数组可用于传统DP，此处未使用
int g[N], cnt;          // g[] 是辅助数组，维护当前子序列末尾值；cnt 是当前长度

int main() {
    // 读取输入：持续读取高度直到输入结束（如EOF或换行）
    while (cin >> x) {
        a[++n] = x;  // 将读入的高度存入 a[1..n]
    }

    // ================== 第一问：求最长非递增子序列（LDS）==================

    // 初始化 g[0] 为一个极大值，作为边界
    g[0] = 2e9;  // 保证第一个元素一定能被处理
    cnt = 0;     // 当前非递增序列长度为0

    for (int i = 1; i <= n; i++) {
        // 如果当前导弹高度 <= 当前非递增序列最后一个元素，可直接接上
        if (a[i] <= g[cnt]) {
            g[++cnt] = a[i];  // 扩展序列
        } else {
            // 否则，找到第一个 g[j] < a[i] 的位置 j，用 a[i] 替换它
            // 目的是维持 g 数组的非递增性，并为后续更长序列提供可能

            int l = 1, r = cnt;  // 在 g[1..cnt] 中二分查找
            while (l < r) {
                int mid = (l + r) >> 1;  // 等价于 (l + r) / 2
                if (g[mid] < a[i]) {
                    r = mid;  // 找第一个小于 a[i] 的位置
                } else {
                    l = mid + 1;
                }
            }
            g[l] = a[i];  // 替换该位置，保持结构最优
        }
    }

    // 输出第一问答案：最长非递增子序列长度
    cout << cnt << endl;

    // ================== 第二问：求最少系统数 = 最长上升子序列（LIS）==================

    cnt = 0;           // 重置计数器
    g[0] = -2e9;       // 初始化为极小值，便于第一个元素插入

    for (int i = 1; i <= n; i++) {
        // 如果当前高度大于最后一个上升序列的末尾，则可扩展
        if (a[i] > g[cnt]) {
            g[++cnt] = a[i];
        } else {
            // 否则，在 g[1..cnt] 中找第一个 >= a[i] 的位置进行替换
            // 使用 lower_bound 找到第一个不小于 a[i] 的位置
            int j = lower_bound(g, g + cnt + 1, a[i]) - g;
            g[j] = a[i];  // 替换后维持 g 的递增性
        }
    }

    // 输出第二问答案：最少需要的拦截系统数量
    cout << cnt << endl;

    return 0;
}

代码逻辑详解

变量	作用
a[]	存储输入的导弹高度序列
g[]	辅助数组，g[i] 表示长度为 i 的子序列的最后一个元素的最小（或最大）可能值
cnt	当前维护的子序列长度
lower_bound	在有序数组中查找第一个 ≥ 给定值的位置

第一问技巧

• 维护一个非递增的 g 数组。
• 若 a[i] <= g[cnt]，直接追加；
• 否则，用二分找到第一个 g[j] < a[i] 的位置并替换，保证后续能接更多导弹。

第二问技巧

• 实际是求 LIS（最长严格递增子序列）。
• 维护一个递增的 g 数组。
• 使用 lower_bound 找到合适位置插入，模拟贪心分组过程。

---

复杂度分析

• 时间复杂度：O(nlog⁡n)O(nlogn)
  • 每个元素进行一次二分查找，共 nn 次，每次 O(log⁡n)O(logn)
• 空间复杂度：O(n)O(n)
  • 主要用于存储数组 a 和 g

---

总结

问题	转化	方法
一套系统最多拦截数	最长非递增子序列（LDS）	贪心 + 二分
最少系统数	最长严格递增子序列（LIS）	Dilworth 定理 + 贪心

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2301_80837606/article/details/151148459