187. 导弹防御系统（美国导弹防御系统）

技术支持：NEFU AB-IN

关联

文章目录

187.导弹防御系统问题含义代码

187. 导弹防御系统

题意

为了应对来自邻国的威胁，R国更新了导弹防御系统。

防御系统的导弹拦截高度要么继续严格单调上升，要么继续严格单调下降。

例如，如果系统在3和4高度拦截两枚导弹，则系统只能拦截4高度以上的导弹。

考虑一系列来袭导弹的高度，找出将它们全部击落所需的最少防御系统数量。

思路

目标是将给定序列拆分为尽可能少的升序和降序子序列。

如何使用dfs 求最小值

迭代加深并设置最小值，并在每次更新时（本次获取）

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

定义子序列的最后一个元素。

使用两个数组，一个是上一个，另一个是分别存储当前所有升序和降序子序列的最后一个元素。 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] 放入现有的降序子序列中。

如果没有合适的降序子序列，则创建新的降序子序列。

代码

进口

来自重新进口的T

从sys 导入setrecursionlimit、stdin、stdout、退出

从集合Counter、deque、defaultdict 导入

从heapq 导入heapify、heappop、heappush、nlargest、nsmallest

从二等分导入bisect_left, bisect_right

从日期时间导入日期时间，时间增量

从字符串ascii_lowercase、ascii_uppercase 导入

从gcd、sqrt、fabs、ceil、floor 导入数学日志

从输入导入TypeVar、List、Dict、Any、Union、Generic

类型=TypeVar(\’类型\’)

数据结构

SA类（通用[类型]）:

def __init__(自身， x: 类型， y: 类型):

self.x=x

自我.y=y

def __lt__(self, other: \’SA[类型]\’) – bool:

返回self.x other.x

def __eq__(self, other: \’SA[类型]\’) – bool:

返回self.x==other.x 和self.y==other.y

def __repr__(self) – str:

返回f\’SA(x={self.x}, y={self.y})\’

持续的

N=int(2e5 + 10) # 如果使用AR，请相应更改

M=int(20) # 如果使用AR，请相应更改

INF=int(2e9)

偏移量=int(100)

# 设置递归限制

设置递归限制(INF)

读

input=lambda: stdin.readline().rstrip(\’\\r\\n\’) # 如果有多个数据则删除

读取=lambda: 映射（int，input（）.split（））

read_list=lambda: 列表(map(int, input().split()))

#放克

类std:

Letter_to_num=staticmethod(lambda x: ord(x.upper()) – 65) # A – 0

num_to_letter=staticmethod(lambda x: ascii_uppercase[x]) # 0 – A

数组=静态方法(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)

过滤器=staticmethod(lambda func, iterable: 列表(过滤器(func, 可迭代)))

@静态方法

def find(container: Union[List[TYPE], str], value: TYPE) – int:

\’\’\’返回容器内值的索引。如果未找到该值，则返回-1。 \’\’\’

if 是实例（容器，列表）:

尝试：

返回容器的索引（值）

除了ValueError:

返回-1

elif 是实例（容器，str）:

返回容器.find(值)

向量

def min_defense_systems(n, 高度):

全局分辨率

回复=n

向上=std.array(0, n)

向下=std.array(0, n)

def dfs(u, su, sd):

全局分辨率

修剪

如果su + sd=res:

返回

如果你==n:

分辨率=分钟（分辨率，su + sd）

返回

对于我在范围内(su):

如果顶部[i]高度[u]:

tmp=向上[i]

顶部[i]=高度[u]

dfs(u+1, 苏， SD)

向上[i]=tmp

休息

: 其他

顶部[su]=高度[u]

dfs(u + 1,su + 1,sd)

对于我的范围（sd）:

向下[i]高度[u]:

tmp=向下[i]

底部[i]=高度[u]

dfs(u+1, 苏， SD)

向下[i]=tmp

休息

: 其他

底部[sd]=高度[u]

dfs(u + 1, su, sd + 1)

dfs(0, 0, 0)

返回响应

而True:

n,=读取()

如果n==0:

休息

高度=read_list()

打印（min_defense_systems（n，高度））

#187.以上导弹防御系统相关内容摘自互联网，仅供参考。相关信息请参见官方公告。