5.4 KiB
一、题目描述
为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度 要么 一直 严格单调 上升 要么 一直 严格单调 下降。
例如，一套系统先后拦截了高度为 3 和高度为 4 的两发导弹，那么接下来该系统就只能拦截高度大于 4 的导弹。
给定即将袭来的一系列导弹的高度，请你 求出至少需要多少套防御系统，就可以将它们全部击落。
输入格式
输入包含多组测试用例。
对于每个测试用例，第一行包含整数 n，表示来袭导弹数量。
第二行包含 n个不同的整数，表示每个导弹的高度。
当输入测试用例 n=0 时，表示输入终止，且该用例无需处理。
输出格式
对于每个测试用例，输出一个占据一行的整数，表示所需的防御系统数量。
数据范围
1≤n≤50
输入样例：
5
3 5 2 4 1
0
输出样例：
2
样例解释
对于给出样例，最少需要两套防御系统。
一套击落高度为 3,4的导弹，另一套击落高度为 5,2,1 的导弹。
二、 题目解析
1、分析
导弹拦截高度要么一直上升要么一直下降。
有的导弹拦截系统可以选择上升，有的可以选择下降，不是单纯地问 所存在的序列可以划分为多少组上升子序列 的问题 狄尔沃斯定理，所以不能用之前的方法解。
2、思路
使用 暴搜
从问题的解出发，最终问题的答案是有许多单调上升子序列和许多单调下降子序列，对于每个数，思考分别将该数放到上升序列中还是下降序列中,不断走二叉树的不同分支。
3、题解
up[] 存储当前所有上升子序列的末尾元素
down[] 存储当前所有下降子序列的末尾元素
Q:如何进行搜索?
假设现在要把一个数放入一个上升序列，那么一定是 所有能放入的上升序列中，最后一个元素最大的那一个。
理由：既然每个数字都要放到一个序列中，对于上升序列，肯定是目前越小越有用，既然能放入大的里面，何必浪费一个小的呢。 注意:
up[i]按这种策略已经是排好序的了，所以只用找最先碰到的一个就行了
三、dfs
时间O(n*2^n) 空间O(n)
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
const int INF = 0x3f3f3f3f;
int n;
int a[N];
int up[N], down[N];
int res;
// 本题关键字：贪心+爆搜
/*
功能：暴搜所有可能，配合剪枝，找出最少的拦截系统数量
u: 第几个导弹
ul: 上升拦截系统的数量，配合up 数组使用
dl: 下降拦截系统的数量，配合down数组使用
*/
void dfs(int u, int ul, int dl) {
if (ul + dl >= res) return; // 伟大的剪枝，不剪枝会TLE~,中途发现已经大于等于res的情况，就返回
if (u == n) { // 走完全程,收集答案
res = ul + dl; // 因为上面的剪枝，把ul+dl>=res的全干掉了，能到这里的，都是<res的，都可以用来更新答案
return;
}
// 放入上升序列
int k = 0;
// 如果把当前导弹使用上升序列的拦截系统进行拦截，那个选择哪个系统呢？
for (k = 0; k < ul; k++)
if (up[k] <= a[u]) break; // up[0],up[1],up[2],... 这样套拦截系统，其数值来讲，是递减的，因为是因为不能再拦截高度更低的才创建了一套新的拦截系统
// 找出放到哪个拦截系统上去，结果为k
int t = up[k]; // 尝试在第k套系统进行拦截第u个导弹,那么，第u个导弹的高度就是第k套系统的新高度
up[k] = a[u]; // 问题是，我们也不一定非得让第u个导弹使用上升序列拦截系统，也可能使用下降序列拦截系统，所以需要记录当前值，回溯后，尝试下降序列拦截
if (k < ul) // 如果当前这些套拦截系统中可以找到某一套进行拦截
dfs(u + 1, ul, dl); // 接到了某个队伍后面去了，修改队伍的最后最大值即可，队伍数量没有长大
else // 如果当前这些套拦截系统中无法找到某一套进行拦截
dfs(u + 1, ul + 1, dl); // 没有找到任何一个符合最后一个高度小于a[u]的队伍，只能多开一队，up数组长度长大1
up[k] = t; // 回溯
// ----------------------------------------------------------------------
// 放入下降序列
k = 0;
for (k = 0; k < dl; k++)
if (down[k] >= a[u]) break;
t = down[k]; // 保留现场
down[k] = a[u];
if (k < dl)
dfs(u + 1, ul, dl);
else
dfs(u + 1, ul, dl + 1);
down[k] = t; // 回溯
}
int main() {
while (cin >> n, n) { // 多套数据，输入n=0时停止
for (int i = 0; i < n; i++) cin >> a[i];
res = INF; // 防御系统的最少数量
dfs(0, 0, 0); // 开始深搜，更新res的值
printf("%d\n", res);
}
return 0;
}