AcWing 482. 合唱队形(Python3)
原题链接
简单
作者:
跂未
,
2024-03-27 21:59:55
,
所有人可见
,
阅读 3
# 我们可以把队列中最高的身高定位k,那么根据k的定位不同
# 可以得到不同的答案,我们只要求其中最长的
# 有了k之后可以将队列看成一个正序最长上升子序列,
# 和一个逆序最长上升子序列
n = int(input())
h = []
h.extend([0] + list(map(int, input().split())))
# f[i]集合表示的是从1到i的上升子序列,存储的是其中的最大值,g同理
f, g = [0] * (n+1), [0] * (n+1)
# 求正序最长上升子序列
for i in range(1, n + 1):
f[i] = 1
for j in range(1, i):
if h[i] > h[j]:
f[i] = max(f[i], f[j] + 1)
#求逆序最长上升子序列
for i in range(n, 0, -1):
g[i] = 1
for j in range(n, i, -1):
if h[i] > h[j]:
g[i] = max(g[i], g[j] + 1)
# 遍历k的不同位置求的,最大的和
ans = 0
for k in range(1, n+ 1):
ans = max(ans, f[k] + g[k])
# ans中k被加了两次,所以n-ans多减了1次k
print(n-ans+1)