【贪心, DFS, 回溯】导弹防御系统「动态规划之LIS模型」

题目

187. 导弹防御系统 - AcWing题库

---

为了对抗附近恶意国家的威胁， $R$ 国更新了他们的导弹防御系统。

一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。

例如，一套系统先后拦截了高度为 $3$ 和高度为 $4$ 的两发导弹，那么接下来该系统就只能拦截高度大于 $4$ 的导弹。

给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

输入格式

输入包含多组测试用例。

对于每个测试用例，第一行包含整数 $n$ ，表示来袭导弹数量。

第二行包含 $n$ 个不同的整数，表示每个导弹的高度。

当输入测试用例 $n=0$ 时，表示输入终止，且该用例无需处理。

输出格式

对于每个测试用例，输出一个占据一行的整数，表示所需的防御系统数量。

数据范围

$1 \le n \le 50$

输入样例：

5
3 5 2 4 1
0

输出样例：

2

样例解释

对于给出样例，最少需要两套防御系统。

一套击落高度为 $3,4$ 的导弹，另一套击落高度为 $5,2,1$ 的导弹。

解题

方法一：贪心 暴搜

思路

本题是【动态规划, 贪心】拦截导弹第二问的升级版。

求的是序列最少可以拆分成多少个不升子序列和不降子序列，用到贪心算法。

但本题最麻烦的地方在于没有指定制导系统是不升子序列还是不降子序列，但是结合着 $1 \le n \le 50$ 的数据范围推测本题可以暴搜每一颗导弹是属于不升子序列亦或是不降子序列，又属于哪一个不升子序列亦或是哪一个不降子序列。

暴搜具体实现见代码及注释。

贪心策略

不升子序列

对于某个数：

• 如果存在结尾大于等于当前数的子序列，则把该数加入结尾大于等于该数的最小的子序列后面；
• 如果现有的子序列结尾均小于当前数，则创建新的子序列以放入该数。

不降子序列

对于某个数：

• 如果存在结尾小于等于当前数的子序列，则把该数加入结尾小于等于该数的最大的子序列后面；
• 如果现有的子序列结尾均大于当前数，则创建新的子序列以放入该数。

证明

见 1.2.2 最长上升子序列模型（二） - AcWing 中 19:06 处。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 60;
    static int n, ans;
    // inc: 维护不降子序列的结尾数们  dec: 维护不升子序列的结尾数们
    static int[] a = new int[N], inc = new int[N], dec = new int[N];
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        // 输入数据知道遇到0
        while (in.nextToken() != in.TT_EOF && (n = (int) in.nval) != 0) {
            for (int i = 0; i < n; ++i) {
                in.nextToken();
                a[i] = (int) in.nval;
            }
            // 初始化最少防御系统数量为导弹数量
            ans = n;
            dfs(0, 0, 0);
            System.out.println(ans);
        }
    }
    
    // i: 当前扫描到的数字  incCnt: 不降子序列的数量  dec: 不升子序列的数量
    static void dfs(int i, int incCnt, int decCnt) {
        // 剪枝: 如果子序列数量之和比当前的答案还大 就必然不可能是最优方案
        if (incCnt + decCnt >= ans) return;
        // 递归出口: 扫描完成
        if (i == n) {
            // 上面剪枝已经剪过了非更优的方案 直接更新最优方案即可
            ans = incCnt + decCnt;
            return;
        }
        int j = 0; // 扫描子序列用到的下标
        // 扫描现存子序列 查找是否存在结尾小于等于当前数的子序列
        // 由于不降子序列是以以上的贪心策略依次加入inc中的 所以inc中的子序列结尾一定是非递减的
        // 这导致如果能找到结尾小于等于该数的子序列 那它一定是满足条件的*最小*结尾子序列
        while (j < incCnt && inc[j] > a[i]) ++j;
        if (j < incCnt) {
            // 如果存在
            int bak = inc[j]; // 先备份一下即将要被覆盖的子序列结尾数 以便之后回溯恢复
            inc[j] = a[i]; // 把该数加入结尾大于等于该数的最小的子序列后面
            dfs(i + 1, incCnt, decCnt); // 搜索下一个数字
            inc[j] = bak; // 回溯
        } else {
            // 如果不存在
            inc[j] = a[i]; // 维护一个新的子序列来放当前数
            dfs(i + 1, incCnt + 1, decCnt); // 搜索下一个数字(创建新了的子序列所以incCnt增加了)
            // 之所以不需要回溯是因为inc中存储的不升子序列的数量只体现在了incCnt上
            // 上面的incCnt没被覆盖而只作为参数传入下一次搜索 对之后的搜索可能创建的新的子序列没有影响
        }
        
        j = 0; // 初始化扫描子序列用到的下标
        // 执行不升子序列的贪心策略并搜索+回溯 与上面的代码类比起来基本一致 不再做注释
        while (j < decCnt && dec[j] < a[i]) ++j;
        if (j < decCnt) {
            int bak = dec[j];
            dec[j] = a[i];
            dfs(i + 1, incCnt, decCnt);
            dec[j] = bak;
        } else {
            dec[j] = a[i];
            dfs(i + 1, incCnt, decCnt + 1);
        }
    }
}