算法提高课笔记（四）

187. 导弹防御系统

为了对抗附近恶意国家的威胁，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.迭代加深。（DFS维护最小值，知识点来了！！！）

---

题解一：DFS记录全局最小值。

时间复杂度：O(n*2^n)。2^n是枚举状态的总数量，n是搜索的次数。

首先要确定当前扫描的数该放入上升子序列还是下降子序列，这一步只能爆搜。

然后延续前一题，分别开一个数组维护所有上升/下降子序列的最后一个导弹高度，保持整个数组的单调性，然后搜索决策如何放置当前数（可以用二分加快搜索）。

题解一相比题解二还是更好写的！

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 55;
int n,ans; // 剪枝，优化关键，ans作为DFS维护的全局最小值
int q[N],up[N],down[N];

void dfs(int u,int su,int sd){
    if (su + sd >= ans) return; // 只有最小值才需要计算
    if (u == n){ // 已经把所有数都搜索完了，计算答案
        ans = su + sd;
        return;
    }

    // 情况1 ： 将当前数放到上升子序列
    int  k = 0;// up[]的范围（也就是k扫描的范围）是0到su-1
    while (k < su && up[k] >= q[u]) k ++;
    // up数组是下降的，对于当前数，在当前所有上升序列的末尾高度中，找到离它最近且比它小的数
    int t = up[k];
    up[k] = q[u];
    if (k < su) dfs(u+1,su,sd);
    else dfs(u+1,su+1,sd);
    up[k] = t; // 恢复现场

    // 情况2 ： 将当前数放到下降子序列
    k = 0;
    while (k < sd && down[k] <= q[u]) k ++;
    // down数组是上升的，对于当前数，在当前所有下降序列的末尾高度中，找到离它最近且比它大的数
    t = down[k];
    down[k] = q[u];
    if (k < sd) dfs(u+1,su,sd);
    else dfs(u+1,su,sd+1);
    down[k] = t; // 恢复现场
}

int main(){

    while (cin >> n,n){
        for (int i = 0;i < n;i ++) cin >> q[i];
        
        ans = n; // ans维护最小值，每次搜索之前置为一个较大的数
        dfs(0,0,0);
        cout << ans << '\n';
    }
    return 0;
}

二分搜索代码： https://www.acwing.com/activity/content/code/content/128088/。

题解二：DFS迭代加深（BFS版DFS）。

时间复杂度：O(n*2^n)。

迭代加深的意思也就是在dfs函数中添加一个参数来控制迭代次数，1次不能搜到答案，参数+1搜2次，2次不够就3次，直到达到参数的限制范围。这样做的好处是防止答案在浅层而dfs搜索到很深找不到答案。

你会发现迭代加深很像用 BFS 的方法去 DFS。比BFS空间复杂度相对较小，还比DFS搜索答案快。

• 为啥不用BFS搜索？

• 虽然BFS很容易求出最小值，但是空间容易爆炸（需要存下一层的状态量），不容易剪枝。

迭代加深搜索思路类似题解一。

枚举放到上升子序列或者中下降子序列的状态就是：2^50，非常大的数。需要迭代加深和贪心优化。

当答案的深度比较小时，迭代加深会优于全局最小值。

画一下递归搜索树就容易理解迭代加深的过程。

参考题解： https://www.acwing.com/solution/content/52200/。

#include <iostream>
using namespace std;
const int N = 55;
int n;
int q[N],up[N],down[N];

bool dfs(int depth,int u,int su,int sd){ // 返回true表示找到答案，返回false表示没找到答案
    if (su + sd > depth) return false; // 超过搜索最大深度，返回没找到，直接回溯
    if (u == n) return true; // 把所有数都搜索完了，没有超过最大搜索深度，找到答案
    // 枚举放到上升子序列
    int k = 0;
    while (k < su && up[k] >= q[u]) ++ k;
    int t = up[k];
    up[k] = q[u];
    if (k == su && dfs(depth,u+1,su+1,sd)) return true;
    else if (k < su && dfs(depth,u+1,su,sd)) return true;
    up[k] = t;
    
    // 枚举放到下降子序列
    k = 0;
    while (k < sd && down[k] <= q[u]) ++ k;
    t = down[k];
    down[k] = q[u];
    if (k == sd && dfs(depth,u+1,su,sd+1)) return true;
    else if (k < sd && dfs(depth,u+1,su,sd)) return true;
    down[k] = t;
    
    return false;
}

int main(){
    while (cin >> n,n){
        for (int i = 0; i < n; ++ i) cin >> q[i];
        
        int depth = 0;
        while (!dfs(depth,0,0,0)) ++ depth; // 搜索深度是逐渐加大的，所以找到的第一个答案就是最小值
        cout << depth << '\n';
    }
}

题解三：迭代加深+二分优化搜索。

时间复杂度：O(log n*2^n)。

参考题解： https://www.acwing.com/solution/content/8828/。

画个模拟图会更好理解二分过程。

#include <iostream>
using namespace std;
const int N = 55;
int n;
int q[N],up[N],down[N];

bool dfs(int depth,int u,int su,int sd){ // 返回true表示找到答案，返回false表示没找到答案
    if (su + sd > depth) return false; // 超过搜索最大深度，返回没找到，直接回溯
    if (u == n) return true; // 把所有数都搜索完了，没有超过最大搜索深度，找到答案
    // 枚举放到上升子序列
    // up数组是非严格下降的,所以up[su-1]存的就是最小的高度，>=它就只能新开序列
    if (!su || up[su-1] >= q[u]){ // su = 0时要特判一下，放第一个数
        up[su] = q[u]; // 新开序列
        if (dfs(depth,u+1,su+1,sd)) return true;
    }else{
        int l = 0,r = su-1;
        while (l < r){ // 二分找到离q[u]最近的且比它小的数
            int mid = l+r>>1;
            if (up[mid] < q[u]) r = mid;
            else l = mid + 1;
        }
        int t = up[l];
        up[l] = q[u];
        if (dfs(depth,u+1,su,sd)) return true;
        up[l] = t; // 恢复现场
    }
    
    // 枚举放到下降子序列
    // down数组是非严格下降的,所以down[sd-1]存的就是最大的高度，<=它就只能新开序列
    if (!sd || down[sd-1] <= q[u]){ // sd = 0时要特判一下，放第一个数
        down[sd] = q[u];
        if (dfs(depth,u+1,su,sd+1)) return true;
    }else{
        int l = 0,r = sd-1;
        while (l < r){
            int mid = l+r>>1;
            if (down[mid] > q[u]) r = mid;
            else l = mid + 1;
        }
        int t = down[l];
        down[l] = q[u];
        if (dfs(depth,u+1,su,sd)) return true;
        down[l] = t;
    }
    
    return false;
}

int main(){
    while (cin >> n,n){
        for (int i = 0; i < n; ++ i) cin >> q[i];
        
        int depth = 1; // 答案至少是1
        while (!dfs(depth,0,0,0)) ++ depth; // 搜索深度是逐渐加大的，所以找到的第一个答案就是最小值
        cout << depth << '\n';
    }
}