文章目录
题目链接：AcWing187.导弹防御系统
1. 题目描述
为了对抗附近恶意国家的威胁，R国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直 严格单调上升 要么一直 严格单调下降 。
例如，一套系统先后拦截了高度为 3 3 3 和高度为 4 4 4的两发导弹，那么接下来该系统就只能拦截高度大于 4 4 4 的导弹。
给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。
输入格式
输入包含多组测试用例。
对于每个测试用例，第一行包含整数 n n n ，表示来袭导弹数量。
第二行包含 n n n 个不同的整数，表示每个导弹的高度。
当输入测试用例 n = 0 n=0 n=0 时，表示输入终止，且该用例无需处理。
输出格式
对于每个测试用例，输出一个占据一行的整数，表示所需的防御系统数量。
数据范围
1
≤
n
≤
50
1 \leq n \leq 50
1≤n≤50
输入样例：
5
3 5 2 4 1
0
输出样例：
2
样例解释
对于给出样例，最少需要两套防御系统。
一套击落高度为
3
,
4
3,4
3,4 的导弹，另一套击落高度为
5
,
2
,
1
5,2,1
5,2,1 的导弹。
2. 题目分析
这道题与AcWing1010.拦截导弹的不同之处在于，本题可以使用不同的拦截系统，而那道题只能使用同一种拦截系统。
所以本题的大体思路与拦截导弹第二问相同，都是通过贪心来进行构造答案，还要在贪心的外面套一层 d f s dfs dfs 用来决定哪种抉择。
贪心思路：
- 对于严格单调上升：从前往后扫描每一个数，对于每个数：
- 如果现有子序列的结尾都大于等于当前数，则创建新的子序列。
- 将当前数放到结尾小于它的最大的子序列后面。
- 对于严格单调下降：从前往后扫描每一个数，对于每个数：
- 如果现有子序列的结尾都小于等于当前数，则创建新的子序列。
- 将当前数放到结尾大于它的最小的子序列后面。
对这两个贪心思路还要通过一个 d f s dfs dfs 来进行决策，最终找到答案。
3. 代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55;
int n;
int a[N];
int up[N], down[N];
int cnt;
void dfs(int u, int su, int sd)
{
if (su + sd >= cnt) return;
if (u == n)
{
cnt = su + sd;
return;
}
int k = 0;
while(k < su && up[k] >= a[u]) k ++;
int t = up[k];
up[k] = a[u];
if (k < su) dfs(u + 1, su, sd);
else dfs(u + 1, su + 1, sd);
up[k] = t;
k = 0;
while(k < sd && down[k] <= a[u]) k ++;
t = down[k];
down[k] = a[u];
if (k < sd) dfs(u + 1, su, sd);
else dfs(u + 1, su, sd + 1);
down[k] = t;
}
int main()
{
while(~scanf("%d", &n), n)
{
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
cnt = n;
dfs(0, 0, 0);
printf("%d\n", cnt);
}
return 0;
}
4. 时间复杂度
O ( 2 n ) O(2^n) O(2n)
其实，由于在 d f s dfs dfs 中加了一些剪枝，所以实际的复杂度不会高达 2 50 2^{50} 250，所以不会超时。