合唱队-动态规划

题目描述
计算最少出列多少位同学，使得剩下的同学排成合唱队形

说明：

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足存在i（1<=i<=K）使得T1<T2<......<Ti-1<ti>Ti+1>......>TK。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。</ti>

请注意处理多组输入输出！

思路：

1. 对于题目，所有人都已经站好位，不能再改变位置了，只能从当中去掉人组成合唱队。同时，可以考虑中间的人两边没有人的情况（比如两头的两个人，或者这个人太矮周围的人都比他高的情况），但是这种情况基本被pass掉。
2. 计算出每个人左边能出现的最多的人数：
   比如题中所给出的示例：186 186 150 200 160 130 197 200。首先如果第一个数186在中间，左边没有数，就自己一个人，所以是1；第二个数186因为左边那个人跟他一边高，没有比他矮的了，所以也是1；第三个数150，左边的人都比他高，他如果是中间的话左边也他自己一个人，所以还是1；第四个数200，因为不能换位置，所以只能留186或者150，加上自己，就是2...最后再以197为例，左边保留150,160是左边人最多的情况，再加上自己，就是3。所以每个人左边人最多的情况（加上自己）就是（186）1 1 1 2 2 1 3 4（200）。同理，看一下每个人右边可能出现最多的人，这时我们从后往前看。200在最右面，所以自己一个人，是1；197最右面没有比他矮的，自己，是1...160左边一个比他矮的，所以算上自己是2，以此类推。所以每个人右边人做多的情况（加上自己）就是（186）3 3 2 3 2 1 1 1（200）
3. 所以将上面两个划横线的对应相加，就可以得到自己如果是中间的那个人，可以得到的最大的合唱队人数。当然，自己加了两遍，所以得减掉一个自己。另外题目问的是最少去掉的人，所以最后的结果：
   总人数 - 该数所在队列人数 = 需要出队的人数
   代码1：
   dp的顺序查找，时间复杂度O(N^2)

   def left_max(l):
    # 计算每个人左边出现的最多的人数
    # 186 186 150 200 160 130 197 200
    dp = [1] * len(l) # 若左边没有比自己小的数，则为自己本身，所以初始值为1
    for i in range(len(l)): # 从左往右遍历
        for j in range(i):
            if l[j]<l[i] and dp[i]<dp[j]+1:
                dp[i] = dp[j]+1
          # if l[j]<l[i]:
          #     dp[i] = max(dp[i],dp[j]+1) 会超时
    return dp #1 1 1 2 2 1 3 4
              # 从右往左推每个人右边可以站的最多的人数
              # 3 3 2 3 2 1 1 1
   while True:
    try:
        N = int(input())
        ss = list(map(int,input().split()))
        left_s = left_max(ss)
        right_s = left_max(ss[::-1])[::-1]
        sum_s = []
        for i in range(len(left_s)):
            # left_s[i]+right_s[i]-1表示此人是中间位置的人时，合唱队的人数
            sum_s.append(left_s[i]+right_s[i]-1)
        print(str(N-max(sum_s)))
    except:
        break

   代码2：
   二分查找，时间复杂度0(logN)

   import bisect
   def max_l(l,dp):
    dp += [1] # dp[i]表示第i个人左边能够站的最多的人数
    b = [float('inf') for i in range(len(l))] # 往b列表中插入，则初始化应该为无穷大
    b[0] = l[0] # 第一个人
    for i in range(1,len(l)):
        # print(b,l[i])
        pos = bisect.bisect_left(b,l[i])
        # 在 b 中找到 l[i] 合适的插入点以维持有序。
        # print(pos)
        b[pos] = l[i]
        dp += [pos+1]
    return dp
   while True:
   ...