当前位置 博文首页 > 一个混错圈儿的小测试：python：合唱队
计算最少出列多少位同学，使得剩下的同学排成合唱队形
说明：
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，???则他们的身高满足存在i（1<=i<=K）使得T1<T2<......<Ti-1<Ti>Ti+1>......>TK。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
注意不允许改变队列元素的先后顺序
请注意处理多组输入输出！
整数N
最少需要几位同学出列
输入
8
186 186 150 200 160 130 197 200
输出
4def _max(queue):
? ? dp = [1] * len(queue)
? ? for i in range(len(queue)):
? ? ? ? for j in range(i):
? ? ? ? ? ? if queue[i] > queue[j]:
? ? ? ? ? ? ? ? dp[i] = max(dp[i], dp[j]+1)
? ? return dp
import sys
while 1:
? ? try:
? ? ? ? num = int(input())
? ? ? ? height = [int(i) for i in sys.stdin.readline().strip().split()]
? ? ? ? if num == len(height):
? ? ? ? ? ? left = _max(height)
? ? ? ? ? ? right = _max(height[::-1])[::-1]
? ? ? ? ? ? max_student = max([left[i] + right[i] - 1 for i in range(len(left))])
? ? ? ? ? ? print(num - max_student)
? ? except:
? ? ? ? break
