N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形。
用例两行数据，第一行是同学的总数 N ，第二行是 N 位同学的身高，以空格隔开
最少需要几位同学出列
8 186 186 150 200 160 130 197 200
4
由于不允许改变队列元素的先后顺序，所以最终剩下的队列应该为186 200 160 130或150 200 160 130
# 等回头用二分查找实现一遍
def get_max_up_arr(arr, count_num):
arr_line = [1]*count_num
for i in range(count_num):
for j in range(i):
if arr[j] < arr[i]:
arr_line[i] = max(arr_line[i], arr_line[j]+1)
return arr_line
while True:
try:
num_count = input()
arr = list(map(int,raw_input().split(' ')))
left_up_arr = get_max_up_arr(arr, num_count)
right_up_arr = get_max_up_arr(arr[::-1], num_count)[::-1]
least_num = num_count - max([ i+j-1for i,j in zip(left_up_arr,right_up_arr)])
print least_num
except:
break 超时只通过40%, 但感觉算法思路应该是对的 while True: try: N = int(input()) nums = list(map(int, input().split())) f_1 = [] # 每个位置最长左子列长度 f_2 = [] # 每个位置最长右子列长度 for i in range(N): f_1.append(1) f_2.append(1) for j in range(1, N): for k in range(0, j): if nums[j] > nums[k]: f_1[j] = max(f_1[j], f_1[k]+1) if nums[N-1-j] > nums[N-1-k]: f_2[N-1-j] = max(f_2[N-1-j], f_2[N-1-k]+1) max_q = 1 for i in range(N): max_q = max(max_q, (f_1[i] + f_2[i])-1) print(N - max_q) except: break
动态规划和利用单调队列的思想大神们已经讲得很多，本人上传一版自己注释的代码，希望可以对还是不理解此题的朋友有一定帮助
#二分搜索定位函数，自己写此函数，也可用已有库bisect
#搜索元素val在nums中的定位，返回的定位位置i,需满足：
#nums[:i]中所有元素都 < val, nums[i:]中所有元素都 >= val
def binary(nums, val):
l = 0
r = len(nums)-1
while l < r:
mid = (l + r) // 2
if nums[mid] == val:
return mid
elif nums[mid] > val:
#为满足开头说的搜索条件和目的，此处一定不能写成 r = mid - 1
r = mid
else:
l = mid + 1
return r
#计算以每个位置为中心，得到的左侧可以满足单调要求的人数（不包括自己）
def count(nums):
#单调递增队列queue，初始为nums[0]
#每个位置的左侧满足要求的人数count（默认为0）
queue = [nums[0]]
count = [0 for _ in range(len(nums))]
#从1开始遍历即可，因为第一个位置nums[0]左侧无人，count一定为0
for i in range(1, len(nums)):
#当nums[i]大于此位置前出现的最大值时，左侧满足要求的人数即为len(queue)
if nums[i] > queue[-1]:
count[i] = len(queue)
queue.append(nums[i])
#否则，进行二分搜索定位并覆盖旧值
#在单调递增队列中的定位位置下标 即为其左侧满足要求的人数
else:
location = binary(queue, nums[i])
queue[location] = nums[i]
count[i] = location
return count
while True:
try:
n = int(input())
nums = list(map(int, input().split()))
assert(n == len(nums))
left_count = count(nums)#得到每个位置左侧满足要求的人数
right_count = count(nums[::-1])[::-1]#得到每个位置右侧满足要求的人数
max_peple = 1#最大人数初始为1
for i in range(len(left_count)):
#当前可组成的最大人数，由于前面计算的左右侧人数不包括自己，需再+1
cur_peple = 1 + left_count[i] + right_count[i]
if cur_peple > max_peple:
max_peple = cur_peple
print(n - max_peple)
except:
break 
import bisect
def lss(seq):
temp, res = [float("inf")]*len(seq), []
for e in seq:
pos = bisect.bisect_left(temp, e)
temp[pos] = e
res.append(pos+1)
return res
while True:
try:
n, heights = int(input()), list(map(int, input().split()))
lm = lss(heights)
rm = lss(heights[::-1])[::-1]
print(n-max(map(sum, zip(lm, rm)))+1)
except:
break while True: try: n = int(input()) A = list(map(int, input().split())) left = [0] * n for i in range(1, n): for j in range(i): if A[j] < A[i] and left[j] + 1 > left[i]: left[i] = left[j] + 1 right = [0] * n for i in range(n - 2, -1, -1): for j in range(n - 1, i, -1): if A[j] < A[i] and right[j] + 1 > right[i]: right[i] = right[j] + 1 ans = 0 for i in range(n): if left[i] > 0 and right[i] > 0: if left[i] + right[i] + 1 > ans: ans = left[i] + right[i] + 1 res = n - ans print(res) except: break
import bisect
def shouldRemoveLeft(team: list) -> list:
cur_team = [team[0]]
removed = [0] * len(team)
i = 1
while i < len(team):
x = team[i]
pos = bisect.bisect(cur_team, x)
removed[i] = removed[i-1] + len(cur_team) - pos
cur_team = cur_team[:pos]
cur_team.append(x)
i += 1
return removed
def numsOfPeopleOutOfTheTeam(team: list) -> int:
if not team&nbs***bsp;len(team) < 3: return 0
dp_left = shouldRemoveLeft(team)
dp_right = shouldRemoveLeft(team[::-1])[::-1]
ans = float('inf')
for i in range(len(team)):
ans = min(dp_left[i] + dp_right[i], ans)
return ans
if __name__ == "__main__":
import sys
i = []
for line in sys.stdin:
i.append(line)
ans = numsOfPeopleOutOfTheTeam(i[1].strip().split())
print(ans)
基本思想是计算最长递增子数列，可以使用两种方法。第一种 left_most() 函数使用动态规划搜索，时间复杂度为 O(N^2)。第二种 left_most_binary() 使用了二分法搜索，可以将时间复杂度降低至 O(NlogN)。中心思想是设置一个排序数列 dp 来存放 arr 里的数，用二分法搜索每个数 arr[i] 插入 dp 的位置，如果该数需要被插入 dp 末尾位置，就增加 dp 的长度。对每个 arr[i]来说，dp 的长度就是 该数左边的最长递增子数列的值。注意 dp 里的数值并不是该递增子数列。
import bisect
def left_most(arr):
# time: O(n^2), space: O(n)
ans = [1]*len(arr)
for i in range(len(arr)):
for j in range(i):
if arr[j]<arr[i] and ans[j]+1>ans[i]:
ans[i] = ans[j]+1
return ans
def left_most_binary(arr):
# time: O(nlogn), space: O(n)
ans = [1]*len(arr)
dp = []
for i in range(len(arr)):
index = bisect.bisect_left(dp, arr[i])
if index==len(dp): dp.append(arr[i])
else: dp[index] = arr[i]
ans[i] = len(dp)
return ans
while True:
try:
n = int(input())
if not n: break
h = list(map(int, input().split(' ')))
left = left_most_binary(h)
right = left_most_binary(h[::-1])[::-1]
ans = max([left[i]+right[i]-1 for i in range(n)])
print (n-ans)
except: break
while True: try: N, num = int(input()), list(map(int, input().split())) dp1, dp2, dp3 = [1]*N, [1]*N, [] for x in range(1, N): for i in range(0, x): if num[i] < num[x]: dp1[x] = max(dp1[x], dp1[i] + 1) for x in range(N-1, -1, -1): for i in range(N-1, x, -1): if num[i] < num[x]: dp2[x] = max(dp2[x], dp2[i] + 1) for x in range(0,N): dp3.append(N+1-dp1[x]-dp2[x]) print(min(dp3)) except: break
def left_max(list): """计算出i这个人，包含自己，在左边符合人数的个数""" res = [1] * len(list) for i in range(len(list)): for j in range(i): if list[j] < list[i] and res[j] + 1 > res[i]: res[i] = res[j] + 1 return res def right_max(list): """计算出i这个人，包含自己，在右边符合人数的个数""" res = [1] * len(list) for i in range(len(list))[::-1]: for j in range(i+1,len(list)): if list[j] < list[i] and res[j] + 1 > res[i]: res[i] = res[j] + 1 return res while True: try: n = int(input()) result = list(map(int,input().split())) left = left_max(result) right = right_max(result) sum_list = [] for i in range(len(left)): sum_list.append(left[i] + right[i]) print(n - (max(sum_list) - 1)) except:
def LittleMan(length, highLs): leftLs = [1 for i in range(length)] rightLs = [1 for i in range(length)] # [1, 1, 1, 2, 2, 1, 3, 4] for i in range(1, length): maxValue = 1 for j in range(0, i): if highLs[i] > highLs[j]: if leftLs[j] + 1 > maxValue: maxValue = leftLs[j] + 1 leftLs[i] = maxValue (3739)# [3, 3, 2, 3, 2, 1, 1, 1] for i in range(length-2, -1, -1): maxValue = 1 for j in range(i+1, length): if highLs[i] > highLs[j]: if rightLs[j] + 1 > maxValue: maxValue = rightLs[j] + 1 rightLs[i] = maxValue allLs = list() for i in range(length): allLs.append(rightLs[i] + leftLs[i] - 1) max_val = max(allLs) return length - max_val if __name__ == "__main__": while True: try: n=int(input()) s=list(map(int,input().split())) res = LittleMan(n, s) print(res) except: break
def updown(h):
res = [1 for i in range(len(h))]
for i in range(len(h)):
for j in range(i):
if h[i] > h[j] and res[i] < res[j] + 1:
res[i] = res[j] + 1
'''
死活过不了。。。复杂度一样
但是估计是用了max函数，所以增加了运行时间。。。
if h[i] > h[j]:
res[i] = max(res[i], res[j] + 1)
'''
return res
while True:
try:
n = int(input())
hArray = list(map(int, input().split()))
resleft = updown(hArray)
resright = updown(hArray[::-1])[::-1]
res = []
for i in range(len(hArray)):
res.append(resleft[i] + resright[i] - 1)
print(n - max(res))
except:
break
import bisect
#动态规划获得最大递增自序列，时间复杂度O(n*n)
# def ascMax(l, dp):
# dp += [1]
# for i in range(1, len(l)):
# tmp = 0
# for j in range(0, i):
# if l[j] < l[i]:
# tmp = max(dp[j], tmp)
# dp += [tmp + 1]
#二分法获取最大递增子序列，时间复杂度O(nlogn)
def ascMax(l, dp):
dp += [1]
b = [float('inf') for i in range(len(l))]#初始化b数组为无穷大
b[0] = l[0](1844)#第一个元素自己就是最大递增子序列
for i in range(1, len(l)):
pos = bisect.bisect_left(b, l[i])
b[pos] = l[i]
dp += [pos + 1]
while True:
try:
N = int(input())
H = list(map(int, input().split(' ')))
dp_1, dp_2 = [], []
ascMax(H, dp_1)
ascMax(H[::-1], dp_2)
dp = []
for i in range(0, N):
dp += [dp_1[i] + dp_2[N-i-1] - 1]
print(N - max(dp))
except:
break
if l[j]<l[i] and ans[j]+1>ans[i]: ans[i]=ans[j]+1 # 每个人的左边出现的最多人(输出左_最长递增子序列) def left_max(l):#l为站成一排的同学序列 ans=[1]*len(l) for i in range(len(l)):# 每个人的游标(从前往后) for j in range(i):# 这个人前面每个人的游标 if l[j]<l[i] and ans[j]+1>ans[i]: ans[i]=ans[j]+1 return ans # 1 1 1 2 2 1 3 4 # 每个人的右边出现的最多人(输出右_最长递增子序列) def right_max(l): ans=[1]*len(l) for i in range(len(l)-1,-1,-1):# 每个人的游标（从后往前） for j in range(i+1,len(l)):# 这个人后面每个人的游标 if l[j]<l[i] and ans[j]+1>ans[i]: ans[i]=ans[j]+1 return ans # 3 3 2 3 2 1 1 1 while True: try: N=int(input())(1177)#8 tall_li_str=input().split() tall_li_int=[int(v) for v in tall_li_str]#[186,186,150,200,160,130,197,200] left_li=left_max(tall_li_int) right_li=right_max(tall_li_int) sum_li=[]#left_li和right_li加和，可以得到每个人如果是中间那个人的话，合唱队最长是多少（自己算两遍） for i in range(len(left_li)): sum_li.append(left_li[i]+right_li[i]) print(N-max(sum_li)+1)#题中问的是最少去几人，也就是总人数减去合唱队最多人数 # 另外加和时自己算了两遍，还得再减去一遍 except: break
import bisect
def deal(l,res):
b = [float('inf')]*len(l)
b[0] = l[0]
res = res+[1]
for i in range(1,len(l)):
pos =bisect.bisect_left(b,l[i])
b[pos]=l[i]
res += [pos+1]
return res
def main(n,s):
n = int(n)
s = list(map(int,s.split()))
dp1, dp2=[], []
dp1 =deal(s,dp1)
dp2 =deal(s[::-1],dp2)[::-1]
return n-max(map(sum,zip(dp1,dp2)))+1
while 1:
try:
print(main(input(),input()))
except:
exit() 
import sys
def lsi(values):
L = len(values)
def check(vs):
index = 0
L0 = []
D = [-1] + [2000000000 for i in range(L)]
for v in vs:
begin = 0
end = index
# 二分查找
while True:
if end - begin <= 1:
break
mid = (begin + end) / 2
if D[mid] >= v:
end = mid
else:
begin = mid
for tmp in (begin, end):
if D[tmp] < v:
index = max(tmp + 1, index)
D[tmp + 1] = min(D[tmp + 1], v)
L0.append(index)
return L0
L0 = check(values)
values.reverse()
L1 = check(values)
maxim = 0
for i in range(L):
maxim = max(L0[i] + L1[L - i - 1] -1, maxim)
return max(max(L0), max(L1), maxim)
while True:
N = sys.stdin.readline().strip()
if not N:
break
values = [int(i) for i in sys.stdin.readline().strip().split(' ')]
print len(values) - lsi(values)
def get_index(nums,target): # 返回列表中不小于目标元素的索引
low,high=0,len(nums) # 左开右闭区间
while low<high:
mid=(low+high)//2
if nums[mid]<target:
low=mid+1
else:
high=mid
return low
def increase_lis(l):
sorted_l = [float('inf') for _ in range(len(l))] #巧妙的实现去重,可以理解为去重有序数组
res,sorted_l[0] = [1],l[0]
for i in range(1,len(l)):
pos=get_index(sorted_l,l[i])
res.append(pos+1)
sorted_l[pos] = l[i]
return res
while True:
try:
n=int(input())
a=list(map(int,input().strip().split()))
dp_L=increase_lis(a)
dp_R=increase_lis(a[::-1])[::-1]
max_value=max([dp_L[i]+dp_R[i]-1 for i in range(n)])
print(n-max_value)
except:
break 参照为啥要起名字那位同学,有序数组初始化为定长是精髓,实现插入时自动去重
用 Python 搞动态规划太容易超时超内存了，用 PyPy 经过 array 优化才跑通：
from array import array
def max_inc_sub(nums=None):
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return dp
while True:
try:
total = int(input())
heights = array("I", [int(h) for h in input().split()])
inc1 = max_inc_sub(heights)
inc2 = max_inc_sub(heights[::-1])[::-1]
_max = 0
for x1, x2 in zip(inc1, inc2):
_max = max(_max, x1 + x2)
print(total - _max + 1)
# print(total - max([x1 + x2 for x1, x2 in zip(inc1, inc2)]) + 1)
except Exception as e:
break
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
