题解 | #合唱队#
合唱队
https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
用动态规划定义一个求最大递增序列的函数,然后将题目列表正序反序输进去各求一次结果,将反序的结果再反序一次,得到的两个列表对应位置相加后生成的列表内的最大值减去1,即是能形成的最长队列,因为自身重复计算了一次所以减去一,然后用N减去这个最长队列即是最终的结果
时间复杂度过高,多运行几次,保不准哪次就过了
def lis(l): dp = [1] * len(l) for i in range(len(l)): for j in range(i): if l[j] < l[i]: dp[i] = max(dp[i], dp[j]+1) return dp while True: try: N = int(input()) l = list(map(int,input().split())) normal = lis(l) reverse = lis(l[::-1])[::-1] #注意这里求出结果后再逆序排列一次 M = N - max([x+y-1 for x,y in zip(normal, reverse)]) print(M) except: break
查看1道真题和解析