摘要
Title: 187. 导弹防御系统
Tag: dfs
Memory Limit: 64 MB
Time Limit: 1000 ms

187. 导弹防御系统

题意

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

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

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

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

思路

目标是将一个给定的序列分成尽可能少的上升子序列和下降子序列，只能爆搜

用dfs求最小值的方法

迭代加深
设最小值，每次更新（本次采取）

这个问题可以通过递归深度优先搜索（DFS）和剪枝技术来解决。具体思路如下：

定义子序列末尾元素：

用两个数组 up 和 down 分别存储当前所有上升子序列和下降子序列的末尾元素。
up[i] 表示第 i 个上升子序列的末尾元素。
down[i] 表示第 i 个下降子序列的末尾元素。

递归函数设计：

设计一个递归函数 dfs(u, su, sd)，也就是选择这个数 h[u]，它要么在递增序列中，要么在下降序列中。其中：

u 表示当前处理的序列位置。
su 表示当前已建立的上升子序列数量。
sd 表示当前已建立的下降子序列数量。
在递归过程中，不断尝试将当前元素放入已有的上升子序列或下降子序列中，或者创建新的子序列。

剪枝优化：

使用全局变量 min_depth 来记录当前找到的最小子序列数量。
如果在递归过程中，当前子序列数量 su + sd 已经大于或等于 min_depth，则停止搜索（剪枝），因为没有必要继续探索这种情况。

递归结束条件：

如果已经处理完所有元素，即 u == n，更新 min_depth 为当前的子序列数量 su + sd。

递归搜索过程：

尝试将当前元素 h[u] 放入已有的上升子序列中。这里采用贪心思想，去替换在最比 h[u] 小的数，保证兼容性最大（类似最长上升子序列的贪心解法）
如果没有合适的上升子序列，则创建一个新的上升子序列。
类似地，尝试将当前元素 h[u] 放入已有的下降子序列中。
如果没有合适的下降子序列，则创建一个新的下降子序列。
代码

# import
from re import T
from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, gcd, sqrt, fabs, ceil, floor
from typing import TypeVar, List, Dict, Any, Union, Generic

TYPE = TypeVar('TYPE')

# Data structure
class SA(Generic[TYPE]):
    def __init__(self, x: TYPE, y: TYPE):
        self.x = x
        self.y = y

    def __lt__(self, other: 'SA[TYPE]') -> bool:
        return self.x < other.x
    
    def __eq__(self, other: 'SA[TYPE]') -> bool:
        return self.x == other.x and self.y == other.y
    
    def __repr__(self) -> str:
        return f'SA(x={self.x}, y={self.y})'


# Constants
N = int(2e5 + 10)  # If using AR, modify accordingly
M = int(20)  # If using AR, modify accordingly
INF = int(2e9)
OFFSET = int(100)

# Set recursion limit
setrecursionlimit(INF)

# Read
input = lambda: stdin.readline().rstrip("\r\n")  # Remove when Mutiple data
read = lambda: map(int, input().split())
read_list = lambda: list(map(int, input().split()))


# Func
class std:
    letter_to_num = staticmethod(lambda x: ord(x.upper()) - 65)  # A -> 0
    num_to_letter = staticmethod(lambda x: ascii_uppercase[x])  # 0 -> A
    array = staticmethod(lambda x=0, size=N: [x] * size)
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [std.array(x, cols) for _ in range(rows)])
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)
    filter = staticmethod(lambda func, iterable: list(filter(func, iterable)))
    @staticmethod
    def find(container: Union[List[TYPE], str], value: TYPE) -> int:
        """Returns the index of value in container or -1 if value is not found."""
        if isinstance(container, list):
            try:
                return container.index(value)
            except ValueError:
                return -1
        elif isinstance(container, str):
            return container.find(value)

# —————————————————————Division line ——————————————————————

def min_defense_systems(n, heights):
    global res
    res = n
    
    up = std.array(0, n)
    down = std.array(0, n)
    
    def dfs(u, su, sd):
        global res
        
        # 剪枝
        if su + sd >= res:
            return 
        if u == n:
            res = min(res, su + sd)
            return 

        for i in range(su):
            if up[i] < heights[u]:
                tmp = up[i]
                up[i] = heights[u]
                dfs(u + 1, su, sd)
                up[i] = tmp
                break
        else:
            up[su] = heights[u]
            dfs(u + 1, su + 1, sd)
            
        for i in range(sd):
            if down[i] > heights[u]:
                tmp = down[i]
                down[i] = heights[u]
                dfs(u + 1, su, sd)
                down[i] = tmp
                break
        else:
            down[sd] = heights[u]
            dfs(u + 1, su, sd + 1)
    
    dfs(0, 0, 0)
    return res 

while True:
    n, = read()
    if n == 0:
        break
    
    heights = read_list()
    
    print(min_defense_systems(n, heights))