题目描述

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

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

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

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

输入格式
输入包含多组测试用例。

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

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

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

输出格式

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

数据范围

1≤n≤50

输入样例

5
3 5 2 4 1
0 

输出样例：

2

算法1

(DFS,迭代加深,剪枝,贪心) O(n2n)O(n2n)
为了能遍历所有情况，我们首先考虑搜索顺序是什么。

搜索顺序分为两个阶段：

从前往后枚举每颗导弹属于某个上升子序列，还是下降子序列；
如果属于上升子序列，则枚举属于哪个上升子序列（包括新开一个上升子序列）；如果属于下降子序列，可以类似处理。
因此可以仿照AcWing 896. 最长上升子序列 II，分别记录当前每个上升子序列的末尾数up[]，和下降子序列的末尾数down[]。这样在枚举时可以快速判断当前数是否可以接在某个序列的后面。

注意这里的记录方式和上一题稍有不同：

这里是记录每个子序列末尾的数；
上一题是记录每种长度的子序列的末尾最小值。
此时搜索空间仍然很大，因此该如何剪枝呢？

对于第二阶段的枚举，我们可以仿照上一题的贪心方式，对于上升子序列而言，我们将当前数接在最大的数后面，一定不会比接在其他数列后面更差。
这是因为处理完当前数后，一定出现一个以当前数结尾的子序列，这是固定不变的，那么此时其他子序列的末尾数越小越好。

注意到按照这种贪心思路，up[]数组和down[]数组一定是单调的，因此在遍历时找到第一个满足的序列后就可以直接break了。

最后还需要考虑如何求最小值。因为DFS和BFS不同，第一次搜索到的节点，不一定是步数最短的节点，所以需要进行额外处理。
一般有两种处理方式：

记录全局最小值，不断更新； 这种搜索顺序可以参考@一瞬流年丶涅槃同学的题解；
迭代加深。一般平均答案深度较低时可以采用这种方式。后面的代码中采用的是这种方式。

时间复杂度

每个数在第一搜索阶段有两种选择，在第二搜索阶段只有一种选择，但遍历up[]和down[]数组需要 O(n)O(n) 的计算量，因此总时间复杂度是 O(n2n)。

参考文献

java 代码

import java.util.Scanner;
public class Main{

    public static int[] up=new int[55];
    public static int[] down=new int[55];
    public static int[] a=new int[55];
    public static int n;

    //su:上升序列  sd: 下降序列  u：计数 death：深度 上限为n  
    // up[] down[] 数组的每一个下标分别代表的是一个上升序列和一个下降序列，有可能有多个上升序列和下降序列
    public static boolean dfs(int death,int u,int su,int sd){

        // 如果上升序列个数 + 下降序列个数 > 总个数是上限，则回溯
        if(su+sd>death){
            return false;
        }
        //枚举完
        if(u==n){
            return true;
        }

        // 枚举放到上升子序列中的情况
        boolean flag=false;
        for(int i=1;i<=su;i++){
            if(up[i]<a[u]){     //满足上升序列
                int temp=up[i];
                up[i]=a[u];
                while(dfs(death,u+1,su,sd)){    //递归，找下一个数u+1
                    return true;
                }
                up[i]=temp;     //还原
                flag=true;      //这个数加到上升序列的后面
                break;          // 注意由上述证明的贪心原理，只要找到第一个可以放的序列，就可以结束循环了
            }
        }

        //重新创建一个新上升序列
        if(!flag){
            up[su+1]=a[u];
            if(dfs(death,u+1,su+1,sd))     //枚举下一个数,放到上升子序列中
                return true;
        }

        // 枚举放到下降子序列中的情况
        boolean flag1=false;
        for(int i=1;i<=sd;i++){
            if(down[i]>a[u]){     //满足下降序列
                int temp=down[i];
                down[i]=a[u];
                while(dfs(death,u+1,su,sd)){    //递归，找下一个数u+1
                    return true;
                }
                down[i]=temp;     //还原
                flag1=true;      //这个数加到上升序列的后面
                break;          // 注意由上述证明的贪心原理，只要找到第一个可以放的序列，就可以结束循环了
            }
        }

        //重新创建一个新上升序列
        if(!flag1){
            down[sd+1]=a[u];
            if(dfs(death,u+1,su,sd+1))     //枚举下一个数,放到下降子序列中
                return true;
        }

        return false;

    }

    public static void main(String[] agrs){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
              n=sc.nextInt();
              if(n==0){
                return;
             }
             for(int i=0;i<n;i++){
                 a[i]=sc.nextInt();
             }
             //搜索深度
             int death=0;
             //迭代加深搜索
             while(!dfs(death,0,0,0)){
                  death++;
               }
           System.out.println(death);
        }
    }
}