題目描述
計算最少出列多少位同學，使得剩下的同學排成合唱隊形
說明：
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
輸出描述:
最少需要幾位同學出列
示例1
輸入
8
186 186 150 200 160 130 197 200
輸出
4實作
def _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
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/289596.html
標籤：python