题解 | #拦截导弹#

该题两问分开做的，第一个用了动规，max_num数组下标为i的元素表示第i个导弹是某个系统的第max_num[i]发炮弹，如果前i发炮弹中某个第j发炮弹的最低高度并且比当前炮弹高，那么第i发炮弹就在第j发炮弹之后进行拦截，即max_num[i]= max_num[j]+1。max_num中的最大值即为所求。 第二问，设置min_num数组表示最少需要len个拦截系统，min_num[i]表示第i个拦截系统的当前最低高度，遍历一遍炮弹的高度，如果有某个拦截系统的当前高度min_num[j]大于炮弹的高度，就让符合条件的拦截系统中最低高度的拦截系统拦截这个导弹，把min_num[i]等于炮弹高度，否则就新建一个拦截系统拦截这个导弹。

num = int(input())
s = input()
nums = s.split(" ")
for i in range(len(nums)):
    nums[i] = int(nums[i])
# print(nums)
max_num = []
ans_max = 0
for i, x in enumerate(nums):
    tmax = 0
    for j in range(0, i):
        if nums[j] >= x and max_num[j] > tmax:
            tmax = max_num[j]
    if ans_max < tmax + 1:
        ans_max = tmax + 1
    max_num.append(tmax + 1)
# print(max_num)
min_num = []


def solve(x: int):
    tmp = -1
    tmpy = 1001
    for i, y in enumerate(min_num):
        if y >= x and y < tmpy:
            tmpy = y
            tmp = i
    if tmp == -1:
        min_num.append(x)
    else:
        min_num[tmp] = x
    return


for x in nums:
    solve(x)
print(ans_max)
print(len(min_num))