动态规划--每日一练（LIS+层级法）
P1020 [NOIP 1999 提高组] 导弹拦截
目录
1.题目描述
2.解题思路
问题一：计算能拦截的最长长度（最长非递增子序列问题）
问题二：计算系统的数量（最长递增子序列问题）
问题三：LIS的优化版本的代码模板（二分+贪心）
3.代码展示
朴素做法
优化版本
1.题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
一行，若干个整数，中间由空格隔开。
输出格式
两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入
389 207 155 300 299 170 158 65
输出
6
2说明/提示
对于前 50% 数据（NOIP 原题数据），满足导弹的个数不超过 104 个。该部分数据总分共 100 分。可使用O(n2) 做法通过。
对于后 50% 的数据，满足导弹的个数不超过 105 个。该部分数据总分也为 100 分。请使用 O(nlogn) 做法通过。对于全部数据，满足导弹的高度为正整数，且不超过 5×104。
此外本题开启 spj，每点两问，按问给分。
NOIP1999 提高组 第一题
2.解题思路
问题一：计算能拦截的最长长度（最长非递增子序列问题）
具体代码可以参考-->动态规划学习之子序列系列（线性DP）_最长上升子序列算法-CSDN博客
问题二：计算系统的数量（最长递增子序列问题）
通过理解两个名词--“ 最长链划分” & “ 最长反链长度 ” 和一个定理来理解本问题的解题思路
为了通俗理解这两个名词和定理，我们可以用一个生活场景来类比：
场景类比：班级排队分小组
假设班上有一群学生，每个学生有一个身高值，现在要把他们分成若干小组，规则是：
每个小组内的学生必须按身高从高到低排队（类似 “非递增序列”，即链）。
问题：
- 一个小组最多能有多少人？（对应 “最长链长度”）
- 最少需要分多少个小组，才能让所有学生都入组？（对应 “最少链划分”）
同时，有一个特殊现象：
如果两个学生的身高严格递增（比如 A 比 B 矮，且 B 比 C 矮），那么他们不能在同一组（因为组内必须非递增），这样的学生构成 “冲突小组”（对应 “反链”）。
一、什么是 “链”？
定义：
链是一个 “可以排进同一小组” 的学生集合，即他们的身高满足非递增顺序（后面的人不高于前面的人）。
- 例如：身高序列
180, 175, 170可以组成一个链（同一小组）。- 单独一个学生
160也是一个链（小组只有一人）。最长链长度：
一个小组最多能容纳的人数，即原序列中最长的非递增子序列长度（对应导弹拦截问题第一问）。二、什么是 “反链”？
定义：
反链是一个 “完全无法排进同一小组” 的学生集合，即任意两人的身高严格递增（后面的人比前面的人高）。
- 例如：身高序列
160, 170, 180中，任意两人都严格递增，构成反链（三人无法同组）。- 两人
150, 165也构成反链（不能同组）。最长反链长度：
最大的 “冲突小组” 人数，即原序列中最长的递增子序列长度（对应导弹拦截问题第二问的关键）。
三、Dilworth 定理：最少分组 = 最长冲突小组人数
定理通俗版：
“最少需要分多少个小组（链划分），取决于班上最高的‘冲突小组’有多少人（最长反链长度）。”为什么？
- 必要性：
假设最长反链有k人（如160, 170, 180），他们两两不能同组，因此至少需要k个小组。- 充分性：
可以按身高给每个学生分配一个 “层级”（即该学生在最长递增子序列中的位置），同一层级的学生必然能组成非递增小组（链）。
- 例如：层级 1：
180, 175, 170（非递增）；层级 2：160, 155（非递增）。- 层级数恰好等于最长反链长度
k，因此最多需要k个小组。
四、回到导弹拦截问题
- 链：一个导弹拦截系统能拦截的非递增导弹序列（如
389, 300, 299, 170, 158, 65）。- 反链：无法被同一系统拦截的递增导弹序列（如
207, 300）。- 最少系统数 = 最长反链长度：
因为最长递增子序列中的每个导弹都需要单独的系统，而通过层级分配可以证明这些系统足够覆盖所有导弹。📍一句话总结📍
- 链：能一起玩的人（非递增）；反链：完全玩不到一起的人（递增）。
- Dilworth 定理：最少需要分多少组，取决于 “最玩不到一起的一群人” 有多少个。3.代码展示
问题三：LIS的优化版本的代码模板（二分+贪心）
具体代码+思路可参考-->动态规划学习之子序列系列（线性DP）_最长上升子序列算法-CSDN博客
3.代码展示
朴素做法：
#include<bits/stdc++.h>
using namespace std;int dp[100005], a[100005], n;// 计算最长非递增子序列（第一问）
void cal_down() {for (int i = 0; i < n; i++) {dp[i] = 1;}int ma = 1;for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) {if (a[j] >= a[i]) {dp[i] = max(dp[j] + 1, dp[i]);}}ma = max(ma, dp[i]);}cout << ma << endl;
}// 计算最长递增子序列（第二问）
void cal_up() {for (int i = 0; i < n; i++) {dp[i] = 1;}int ma = 1;for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) {if (a[j] < a[i]) {dp[i] = max(dp[j] + 1, dp[i]);}}ma = max(ma, dp[i]);}cout << ma << endl;
}signed main() {// 读取输入while (scanf("%d", &a[n]) != EOF ) {n++;}cal_down(); // 输出最长非递增子序列长度cal_up(); // 输出最长递增子序列长度return 0;
}优化版本：
#include<bits/stdc++.h>
using namespace std;const int MAXN = 100005;
int a[MAXN], n = 0;// 计算最长非递增子序列（第一问）
void cal_down() {vector<int> tails;for (int i = 0; i < n; i++) {auto it = upper_bound(tails.begin(), tails.end(), a[i], greater<int>());if (it == tails.end()) {tails.push_back(a[i]);} else {*it = a[i];}}cout << tails.size() << endl;
}// 计算最少系统数（第二问）
void cal_up() {vector<int> systems; // 每个系统的最后高度（按升序排列）for (int i = 0; i < n; i++) {// 找到第一个大于等于a[i]的系统auto it = lower_bound(systems.begin(), systems.end(), a[i]);if (it == systems.end()) {// 需要新系统systems.push_back(a[i]);} else {// 更新该系统的最后高度*it = a[i];}}cout << systems.size() << endl;
}signed main() {while (n < MAXN && scanf("%d", &a[n]) != EOF) {n++;}cal_down(); // 输出最长非递增子序列长度cal_up(); // 输出最少系统数return 0;
}