题解 | #合唱队#

原理

动态规划(DP问题)之最长上升子序列(LIS)
LIS问题的变形。求最少出列人数==求最多剩余人数，即求这个驼峰数列的最长长度。
将问题分解成两部分：驼峰左边是最长上升子序列、驼峰右边是最长下降子序列，求出两边序列长度之和的最大值即可。

my code

def LIS(arr):
    # 求最大上升子序列
    sub = []
    for i in range(len(k)):
        sub.append(1)
        for j in range(i):
            if k[j] < k[i] and sub[j]+1 > sub[i]:
                sub[i] = sub[j] + 1
    return sub

while True:
    try:
        N = int(input())
        k = input().split()
        k = [int(item) for item in k]

        up = LIS(k) # 最大上升子序列
        k = k[::-1]
        down = LIS(k)[::-1] # 最大下降子序列，反转x2
        length = 1
        for i in range(len(k)):
            length = up[i] + down[i] -1 if up[i] + down[i] > length else length # 每个位置作为峰时的序列长度，取最大
        print(N-length)
    except:
        break