[AcWing] 187. 导d防御系统（C++实现）最长上升子序列模型+贪心+dfs爆搜

[AcWing] 187. 导d防御系统（C++实现）最长上升子序列模型+贪心+dfs爆搜

• 1. 题目
• 2. 读题（需要重点注意的东西）
• 3. 解法
• 4. 可能有帮助的前置习题
• 5. 所用到的数据结构与算法思想
• 6. 总结

1. 题目

2. 读题（需要重点注意的东西）

读题：
在[AcWing] 1010. 拦截导d（C++实现）最长上升子序列模型+贪心的基础上，多了一个条件：导d拦截系统可以是 严格上升 的子序列，也可以是 严格下降 的子序列，题目中给出的数各不相同。

思路： 最长上升子序列 + 贪心 + dfs
在[AcWing] 1010. 拦截导d（C++实现）最长上升子序列模型+贪心的基础上，需要考虑导d拦截系统是上升的还是下降的两种情况，用dfs来爆搜每一个节点放在上升系统和下降系统中这两种情况。

分别记录当前每个上升子序列的末尾up[]，和下降子序列的末尾数down[]，以便于在枚举时可以快速判断当前数是否可以接在某个序列的后面：

1. 如果是上升子序列，放在最大的小于当前数（贪心）的上升子序列末尾之后，由于上升子序列结尾是单调的，因此找到第一个末尾数值小于当前数的序列（可以加上二分来优化）之后就可以断开搜索（剪枝优化）；
2. 如果是下降子序列，放在最小的大于当前数（贪心）的上升子序列之后，由于下降子序列结尾是单调的，因此找到第一个末尾数值大于当前数的序列（可以加上二分来优化）之后就可以断开搜索（剪枝优化）；
3. 当上升序列的数量+下降序列的数量大于当前的全局最小值，剪枝。
   

如何得到防御系统数量的最小值？

1. 维护一个全局最小值
2. 迭代加深

考虑到数据范围在50以内，是可以使用dfs爆搜的。

3. 解法

---------------------------------------------------解法---------------------------------------------------

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 60;
    static int res;
    static int n;
    static int[] a;
    static int[] up = new int[N];
    static int[] down = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        while (true){
            n = Integer.parseInt(reader.readLine());
            res = Integer.MAX_VALUE;
            if(n == 0) break;
            String[] s = reader.readLine().split(" ");
            a = new int[s.length];
            for(int i = 0;i < n;i++) a[i] = Integer.parseInt(s[i]);
            dfs(0,0,0); // dfs遍历
            System.out.println(res);
        }
    }

    /**
     *
     * @param u 表示当前遍历到第几个导d了
     * @param su 上升序列个数
     * @param sd 下降序列个数
     */
    public static void dfs(int u, int su, int sd){
        // 剪枝
        if(su + sd >= res) return;
        if(u == n){
            res = Math.min(res,su + sd);
            return;
        }

        // 将当前值放在上升子序列中
        int ku = 0; // k_up
        while(ku < su && up[ku] > a[u]) ku++; // 找第一个末尾值小于当前值的序列（剪枝）
        int tempu = up[ku]; // 用于恢复现场
        up[ku] = a[u];
        if(ku < su) dfs(u+1,su,sd); // 如果k小于当前上升子序列的个数，说明不用开新的上升子序列
        else dfs(u+1,su+1,sd);
        up[ku] = tempu;

        // 将当前值放在下降子序列中
        int kd = 0; // k_down
        while(kd < sd && down[kd] < a[u]) kd++; // 找第一个末尾值大于当前值的序列（剪枝）
        int tempd = down[kd]; // 用于恢复现场
        down[kd] = a[u];
        if(kd < sd) dfs(u+1,su,sd); // 如果k小于当前下降子序列的个数，说明不用开新的下降子序列
        else dfs(u+1,su,sd+1);
        down[kd] = tempd;
    }
}

---

可能存在的问题

4. 可能有帮助的前置习题

• [AcWing] 1010. 拦截导d（C++实现）最长上升子序列模型+贪心

5. 所用到的数据结构与算法思想

• 动态规划
• 最长上升子序列问题
• 贪心

6. 总结

最长上升子序列模型，可以发展为不同的最长上升子序列题目

最长上升子序列模型的特征（不需要都满足）：
1. 以每个点为终点都要判断一遍
2. 路径为一条上升子序列（或下降子序列）
3. 要求的数列会呈如下分布：

贪心的证明策略一般采用反证法：
加设当前贪心法和最优解法不同，再反推出不可能的情况
证明出当前贪心法就是最优解。