题解 | #合唱队#
合唱队
https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
n = int(input()) i = input().split() i = list(map(int, i)) zuo = [0] you = [0] for h in range(1, n): jilu = [] for k in range(h): if i[h] > i[k]: jilu.append(zuo[k]) if len(jilu) == 0: zuo.append(0) else: zuo.append(max(jilu) + 1) i=i[::-1] for h in range(1, n): jilu = [] for k in range(h): if i[h] > i[k]: jilu.append(you[k]) if len(jilu) == 0: you.append(0) else: you.append(max(jilu) + 1) you=you[::-1] he=[] for a in range(n): if zuo[a]>0 and you[a]>0: he.append(zuo[a]+you[a]) q=max(he) print(n-q-1)
题目可以等价为求最长的合唱队形的长度,那么我们可以求出每一个人作为中间人时合唱队形长度的最大值,然后再取最大值就行了。
对于第i个人,我们记他左边的合唱队形最长为zuo[i],则有zuo[i]=zuo[k]+1,其中,k是i左边比i矮的人中,zuo[k]值最大的人。
依据这个公式我们就可以从推出所有人的“左合唱队形"的最大值,同理可以求出”右合唱队形“的最大值,两者相加再+1即为最长的合唱队形。