题解 | #合唱队#

优化了一下别人的代码，应该更易读些

import bisect as bi

def ldp(h): # 动态规划
    L=len(h)
    dp=[1]*L # 若左边没有比自己小的数，则为自己本身，所以初始值为1
    for i in range(L): # 从左往右遍历
        for j in range(i): # 实现状态转移
            if h[j]<h[i] and dp[i]<dp[j]+1:
                dp[i]=dp[j]+1
    return dp

def ldp_bi(h): # 二分查找维护上升序列
    M=max(h)
    lnum=[M+1]*len(h) # 初始状态全部比最大身高还要大
    lmax=[]
    for i in h:
        loc=bi.bisect_left(lnum,i)
        lnum[loc]=i # 找到第一个身高满足i>h[loc]的位置，更新上升序列
        lmax.append(loc+1) # i对应的最大上升序列长度为loc+1
    return lmax

while True:
    try:
        n=eval(input())
    except EOFError:
        break
    else:
        h=[eval(a) for a in input().split()]
        m=[i+j for i,j in zip(ldp_bi(h),ldp_bi(h[::-1])[::-1])]
        print(n-max(m)+1)