动态规划：华为练习题：合唱队排队

Bertha 。 2023-07-02 11:28 45阅读 0赞

题目描述
    计算最少出列多少位同学，使得剩下的同学排成合唱队形
    说明：
    N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 
    合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，   则他们的身高满足存在i（1<=i<=K）使得T1<T2<......<Ti-1<Ti>Ti+1>......>TK。 
    你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 
    
    输入描述:
    整数N
    
    输出描述:
    最少需要几位同学出列
    
    示例1
    输入
    8
    186 186 150 200 160 130 197 200
    输出
    4
    '''           
            
    #list1=[186,186,150,200,160,130,197,200]
    #list1=[186,186,150,200,201,210,151,152,153]
    #list1=[150,186,186,170]
    #n=len(list1)
    '''
    方法1：利用bisect_left函数，每次寻找该元素在序列中的绝对位置，我们
    用一个数组来记录顺序递增数列的寻找情况，首先在数组中插入原数组的第一个数，每次
    插入新的数时都扫描一次递增数组，按照顺序情况找到该数的位置，并替换当前的数，即这个数列
    会不断更新我们所找到的最长递增字串，如插入200时，最长递增字串为150，200
    插入160时最长字串为150，160，这时数列的意义在于我们找到了最长递增字串，但是
    会有新的子串数进行覆盖，即arr[i]代表能找到的当前数组位置能找到的子串的最后一位
    数字，我们可以不必找到最大的顺序子串（因为最大顺序子串是不唯一的，只需要记录最后
    一位数字就行了
    '''
    import bisect
    while True:
        try:        
            n=int(input())
            list1=list(map(int,input().split()))    
            def find_sort_arr(list1,n):    
                arr=[99999999]*n 
                arr[0]=list1[0]
                res=[]
                res+=[1]
                for i in range(1,len(list1)):
                    pos=bisect.bisect_left(arr,list1[i])
                    res.append(pos+1)
                    arr[pos]=list1[i]
                    #print(pos,list1[i],arr)
                return res
            res1=find_sort_arr(list1,n)
            #对数列反转进行最大递减数列
            res2=find_sort_arr(list1[::-1],n)[::-1]
            result_arr=list(map(lambda x,y:x+y,res1,res2))            
            print(n-(max(result_arr)-1))    
        except:
            break
    
    
    #方法2
    '''
    1、首先寻找最大顺序字序列，即a<b<c<d    
    计算方法为先记录第一个数顺序在当前序列的位置，再选择下一个数，并和前面的数比较此时这个数的
    当前位置，并记录比当前数小的数的序列，选择最大序列值+1,直到所有的数都被选择完毕
    比如186 186 150为 1 1 1，那么当插入200时，比200小的数位186 186 150，对应的顺序序列位置
    1 1 1，max([1,1,1])=1，所以200对应的顺序序列为2,我们用max_num来存储前n-1个属于n的字序列的
    最大序列值，不过这个方法的弱点在于必须对i-1个数都进行一次遍历，所以其时间复杂度为n2。相比于
    方法1.方法2的时间复杂度更高
    '''
    while True:
        try:
            num=int(input())
            list1=list(map(int,input().split()))
            #1、首先寻找最大顺序字序列，即a<b<c<d    
            # 计算方法为先记录第一个数顺序在当前序列的位置，再选择下一个数，并和前面的数比较此时这个数的当前位置，并
            #记录比当前数小的数的序列，选择最大序列值+1,直到所有的数都被选择完毕
            order_arr=[1]
            for i in range(1,num):
                max_num=0
                for j in range(0,i):
                    target=list1[i]
                    if target>list1[j]:
                        cur_order=order_arr[j]
                        if cur_order>max_num:
                            max_num=cur_order
                order_arr.append(max_num+1)
            #print(order_arr)                
            #2、计算最大逆向序列
            order_arr1=[1]
            list2=list1[::-1]
            for i in range(1,num):
                max_num=0
                for j in range(0,i):
                    target=list2[i]
                    if target>list2[j]:
                        cur_order=order_arr1[j]
                        if cur_order>max_num:
                            max_num=cur_order
                order_arr1.append(max_num+1)
            #print(order_arr1[::-1])                
            order_arr2=order_arr1[::-1]
            result_arr=list(map(lambda x,y:x+y,order_arr,order_arr2))            
            print(len(list1)-(max(result_arr)-1))    
        except:
            break