题解 | 合唱队

n^2的基础dp,理论上应该能够直接用n^2通过，但是Python3不太给力，用Pypy3就可以了/

n = int(input())
ans = 0
lst = list(map(int,input().split()))
dpl = [0 for x in range(n)]
dpr = [0 for x in range(n)]
for i in range(n):
    dpl[i] = 1
    for j in range(i):
        dpl[i] = max(dpl[i], dpl[j] + 1) if lst[i] > lst[j] else dpl[i]
for i in range(n - 1,-1,-1):
    dpr[i] = 1
    for j in range(n - 1, i, -1):
        dpr[i] = max(dpr[i], dpr[j] + 1) if lst[i] > lst[j] else dpr[i]
for i in range(n):
    ans = max(ans,dpl[i] + dpr[i] - 1)
print(n - ans)

#牛客春招刷题训练营# + 链接