1999年NOIP提高组导弹拦截（洛谷P1020）：从暴力到最优解
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;
}三、算法核心讲解
1. 最长不上升子序列
2. 最少拦截系统（最长上升子序列）
同样采用贪心+二分优化
lower_bound实现升序查找tails数组始终保持升序排列
四、新手学习建议
原创内容 转载请注明出处
