第一步: 分别求从第一个同学位置
T
0
T_{0}
T0开始到当前同学位置
T
i
T_{i}
Ti,可以达成最长递增子序列的同学数为
n
i
l
e
f
t
n_{i}^{left}
nileft;从当前同学位置
T
i
T_{i}
Ti到最后一个同学位置
T
N
−
1
T_{N-1}
TN−1,可以达成最长递减子序列的同学数为
n
i
r
i
g
h
t
n_{i}^{right}
niright(可以对之后的数列取逆序,然后按求最长递增子序列来求,对结果再取逆序)。
第二步: 从左到右依次以当前同学
T
i
T_{i}
Ti为中心,身高向两边递减,求最少出列的同学个数。为
N
−
(
n
i
l
e
f
t
+
n
i
r
i
g
h
t
−
1
)
N-(n_{i}^{left}+n_{i}^{right}-1)
N−(nileft+niright−1),保存最少的值即可。
核心算法: 最长递增子序列。
算法思想: 动态规划,二分法。
def get_LIS(highs):
n = len(highs)
count = [1]*n
for i in range(1,n):
for j in range(i):
if highs[j] < highs[i]:
count[i] = max(count[i],count[j]+1)
return count
n = input()
n = int(n)
highs = []
highs = input()
highs = [int(high) for high in highs.split()]
ascend_count = get_LIS(highs)
descend_count = get_LIS(highs[::-1])[::-1]
# print(ascend_count)
# print(descend_count)
print(n-max(ascend_count[i] + descend_count[i] - 1 for i in range(n)))
2.2 二分法(
O
(
N
l
o
g
(
N
)
)
O(Nlog(N))
O(Nlog(N)))
def get_LIS_bi(highs):
n = len(highs)
dp = []
dp.append(highs[0])
count = [1]*n
for i in range(1,n):
cur = highs[i]
if cur > dp[-1]:
dp.append(cur)
count[i] = len(dp)
else:
left,right = 0,len(dp)-1
while(left<=right):
mid = (left+right)//2
if dp[mid] < cur:
left = mid + 1
else:
right = mid - 1
dp[left]=cur
count[i] = left+1
return count
n = input()
n = int(n)
highs = []
highs = input()
highs = [int(high) for high in highs.split()]
ascend_count = get_LIS(highs)
descend_count = get_LIS(highs[::-1])[::-1]
# print(ascend_count)
# print(descend_count)
print(n-max(ascend_count[i] + descend_count[i] - 1 for i in range(n)))
如有问题或建议欢迎私信。
严禁私自转载,侵权必究。
参考:
[1] 最长上升子序列 (LIS) 详解+例题模板 (全) [CSDN]
[2] 二分查找之第一个大于小于等于 target 的值 [CSDN]
[3] 题解 | #合唱队# [牛客网]
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)