题目传送门：P1020 [NOIP1999 普及组] 导弹拦截 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这是一道普及题，现在做起来还是比较轻松的，但是当时做这道题花了我半天时间哈哈哈。
题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是 ≤50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
11行，若干个整数（个数 ≤100000）
NOIP 原题数据规模不超过 2000。
输出格式
22行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入
389 207 155 300 299 170 158 65
输出
6 2
说明/提示
为了让大家更好地测试n方算法，本题开启spj，n方100分，nlogn200分
每点两问，按问给分。
思路
第一问很直接，就是找最长不增子序列的长度，用暴力的方法的话只能得一半分，毕竟复杂度O(N ^ 2)谁顶得住啊。
这个其实是一个经典算法LIS（最长递增子序列），会LIS的话，什么最长不增，递减，不减子序列都会了。
具体LIS算法可以看这个：算法 学习笔记（二）: LIS - 知乎 (zhihu.com)
这个算法结合了单调栈，单调栈知识我也找来啦！单调栈 - OI Wiki (oi-wiki.org)
还用到了二分，二分这里也有：二分 - OI Wiki (oi-wiki.org)
不过对于简单已知有序列，我们可以通过lower_bound和upper_bound快速地得到位置。
第一问结束了，第二问怎么办呢？
这里就要知道狄尔沃斯定理(Dilworth's theorem)亦称偏序集分解定理。
我们不需要知道太多，只需要知道“最多的不增子序列的个数” 必然等于 “最长的递增子序列的长度”，这样我们只需要求最长的递增子序列长度就好了，和第一问一样哦。
这里有一个记忆方法：一边是长度，一边是数目，两边的区间正好相对（不增 >= ，递增 < ）。
代码
/*Copyright (C) Eriktse 2022*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9;
int stk[maxn], top = 0;
int a[maxn], N = 0;
signed main()
{
int x;
while(cin >> x)a[ ++ N] = x;
for(int i = 1;i <= N; ++ i)//构造单调不增栈
{
if(top == 0 || a[i] <= stk[top])stk[++ top] = a[i];
else
{
//找到第一个小于a[i]的
int pos = upper_bound(stk + 1, stk + 1 + top, a[i], greater<int>()) - stk;
stk[pos] = a[i];
}
}
cout << top << '\n';
top = 0;
//狄尔沃斯定理：（不连续）不增序列的个数 = （不连续）最长增的序列长度
for(int i = 1;i <= N; ++ i)//构造单调递增栈
{
if(top == 0 || a[i] > stk[top])stk[++ top] = a[i];
else
{
//找到第一个大于等于a[i]的并替换掉
int pos = lower_bound(stk + 1, stk + 1 + top, a[i]) - stk;
stk[pos] = a[i];
}
}
cout << top << '\n';
return 0;
}
文章评论