动态规划 | HJ24 合唱队

# 最优解1
import bisect
def inc_max(l):
    dp = [1]*len(l) # 初始化dp，最小递增子序列长度为1
    arr = [l[0]] # 创建数组
    for i in range(1,len(l)): # 从原序列第二个元素开始遍历
        if l[i] > arr[-1]:
            arr.append(l[i])
            dp[i] = len(arr)
        else:
            pos = bisect.bisect_left(arr, l[i]) # 用二分法找到arr中第一个比ele_i大（或相等）的元素的位置
            arr[pos] = l[i]
            dp[i] = pos+1
    return dp
 
while True:
    try:
        N = int(input())
        s = list(map(int, input().split()))
        left_s = inc_max(s) # 从左至右
        right_s = inc_max(s[::-1])[::-1] # 从右至左
        sum_s = [left_s[i]+right_s[i]-1 for i in range(len(s))] # 相加并减去重复计算
        print(str(N-max(sum_s)))
    except:
        break

# 最优解2
def dp(lst):
    dp = []
    for i in range(len(lst)):
        dp.append(1)
        for j in range(i):
            if lst[j] < lst[i]:
                dp[i] = max(dp[i], dp[j]+1)
    return dp

while True:
    try:
        n = int(input())
        heights = list(map(int, input().split(' ')))
        dp1 = dp(heights)
        dp2 = dp(heights[::-1])[::-1]
        res = []
        for i in range(len(heights)):
            res.append(dp1[i]+dp2[i]-1)
        print(n - max(res))
    except:
        break

# 最优解3
def  maxInc(height):
    n = len(height)
    dp = [1]*n
    #维护一个虚拟递增序列
    que = [height[0]]
    for i in range(1,n):
        if height[i]>que[-1]:
            que.append(height[i])
            dp[i] = len(que)
        #把新值维护到这个递增序列中它能够大于前面所有值的最大位置
        #1.大于最后值,append 2.大于pos-1,小于下标为pos的值,替换pos
        #que长度为递增子序列的最大长度
        #下标i对应的值为 递增序列能包含i+1个数,长度能达到i+1所需要越过的门槛
        #que中维护的是 一个最低代价的达到各递增序列长度的门槛值
        else:
            pos=0
            while que[pos]<height[i]:
                pos +=1
            que[pos] = height[i]
            dp[i]= pos+1
    return dp  
     
while  True:
    try:
        n = int(input())
        height = list(map(int,input().split()))
        inc = maxInc(height)
        dec = maxInc(height[::-1])[::-1]
        max_len = 0
        for i in range(n):
            if max_len< inc[i]+dec[i]-1:
                max_len= inc[i]+dec[i]-1
         
        print(n-max_len)
 
    except:
        break

用时：3h