题解 | #合唱队#

import copy

N = int(input())
heights = list(map(int, input().split(" ")))

def dp_arr(in_list, num):
    lr = [[-1 for _ in range(num)] for _ in range(2)]
    least_slope = [-1 for _ in range(num)]
    for i in range(num):
        for j in range(i, num):
            if i == 0:
                if j == 0:
                    lr[1][j] = 0
                    least_slope[i] = 0
                elif in_list[j] <= in_list[lr[1][j - 1]]:
                    lr[1][j] = j
                else:
                    lr[1][j] = lr[1][j - 1]
            elif lr[1][j - 1] == -1:
                if lr[0][j - 1] == -1:
                    continue
                elif in_list[j] > in_list[lr[0][j - 1]]:
                    lr[1][j] = j
                    least_slope[i] = j
            else:
                if (
                    in_list[j] < in_list[lr[1][j - 1]]
                    and in_list[j] > in_list[lr[0][j - 1]]
                ):
                    lr[1][j] = j
                else:
                    lr[1][j] = lr[1][j - 1]
        if lr[1][-2] == -1 or lr[1][-1] == -1:
            break
        lr[0] = copy.deepcopy(lr[1])
        lr[1] = [-1 for _ in range(num)]
    return lr, least_slope

left2right, left_ls = dp_arr(heights, N)
del left2right
heights_rev = list(reversed(heights))
right2left, right_ls = dp_arr(heights_rev, N)
del right2left

while left_ls[-1] == -1:
    del left_ls[-1]
while right_ls[-1] == -1:
    del right_ls[-1]

left_idx = 0
right_idx = len(right_ls)-1
max_people = 0
i = N*1
for i in range(len(left_ls)):
    for j in range(len(right_ls)):
        if left_ls[i] == -1:
            break
        elif right_ls[j] == -1:
            continue
        elif left_ls[i] + right_ls[j] + 2 <= N:
            max_people = max(max_people, i + j + 2)
        else:
            continue

print(N - max_people)

从左往右扫一遍，目标是得到，当有i个元素的递增序列时，最右端索引最小的元素，即least_slope，其索引i表示几个元素构成的递增序列，元素值表示序列右边最小索引值

从右往左进行同样的过程（把heights reverse一下）

得到这两个slope后，穷举。即，如果left_ls的元素和right_ls元素之和+2不大于总元素个数的情况下（左右递增序列的最高值不对撞），总元素最大的情况（即，此时两个列表的索引相加）

为了减少时间，如果lr[1]的最右边只有一个非-1时退出

为了减少空间，只存两行lr——行存法

不是最优方法，却是第一次靠自己做出来的dp