合唱队形 蓝桥杯 ACWING Python实现

问题描述
　　N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
　　合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。
　　你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入格式
　　输入的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。
输出格式
　　输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
样例输入
8
186 186 150 200 160 130 197 220
样例输出
4

解题思路

1.首先举几个例子：

输入：186 186 150 200 160 130 197 220
保留：150 200 160 130

输入：130 130 174 130 185 230 206 219 210 173
保留：130 174 185 206 219 210 173

输入：130 140 150 160 170 180 190 200
保留：130 140 150 160 170 180 190 200

简单的说，就是保留下来的序列一定要满足这样的规律：单调递增，或者单调递减，或者先递增再递减。

2.探索解题方法：
随意假设输入序列中的一个数字，是保留下来序列中的最大值。我们可以发现，保留下来的序列是这个效果：
单调递增序列，最大值，单调递减序列
比如：

输入：186 186 150 200 160 130 197 220
假设：160是最大的
则保留：150 160 130

由于我们要保留尽可能多的人唱歌，所以我们希望：在所有的可能性中，保留 len(单调递增序列)+len(单调递减序列)的那种可能性（递增或递减序列的长度可以为0）。
那我们就可以通过枚举的方法计算出，任意一位数字是最大值时， len(单调递增序列)+len(单调递减序列)的值。这样我们就可以得到最多能保留的人数了。

3.关于最长上升子序列
如何得到尽可能长的序列？

输入：130 150 174 130 185 230
希望得到：130 150 174 185 230
而不是：130 185 230

可以先用递归的方法从后往前考虑问题：
大概就是：

def 输出列表中的最长上升子序列(list)：
      return [输出列表中的最长上升子序列(list[:-1]), list[-1]]

• 如果结尾是230，首先230的前一个数字X必须是小于230的。并且希望在所有可能的，以X结尾的序列是最长的。找到X为185。
• 现在结尾是185，185的前一个数字X必须是小于185的。并且希望在所有可能的，以X结尾的序列是最长的。找到X为174。
• ......
• 以130结尾的序列最长只可能为1

想明白了就可以从前往后解题了：

• 130结尾的最长上升子序列数为1
• 150结尾的最长上升子序列数为：130结尾+1=2
• 174结尾的最长上升子序列数为：150结尾+1=3
• 130结尾的最长上升子序列数为1
• 185结尾的最长上升子序列数为：150结尾+1=4
• 230结尾的最长上升子序列数为：185结尾+1=5

非常具体的演示可以看这里：
https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/shi-pin-tu-jie-zui-chang-shang-sheng-zi-xu-lie-by-/

定义一个函数，输入一个列表，输出以每一位结尾时，最长上升子序列的长度：

def LIS(ls):
    dp = [1 for i in range(len(ls))]
    for ei,i in enumerate(ls):
        for ej,j in enumerate(ls[:ei]):
            if i>j and dp[ei]<dp[ej]+1:
                dp[ei] = dp[ej]+1
    return dp
# 输入：[130, 130, 174,  130, 185, 230, 206, 219, 210, 173]
# 输出：[1, 1, 3, 1, 4, 7, 5, 7, 6, 2]

这样，如果反着输入列表，就会输出一个：以每一位开始时，最长下降子序列的长度的列表。
把每一位对应相加，就是任意一位数字是最大值时， len(单调递增序列)+len(单调递减序列)的值(不严谨，由于最大值被计算了两边，所以需要再-1)。

len(单调递增序列): [1, 1, 2, 1, 3, 4, 4, 5, 5, 2]
len(单调递减序列): [1, 1, 2, 1, 2, 4, 2, 3, 2, 1]
相加再减一：       [1, 1, 3, 1, 4, 7, 5, 7, 6, 2]

最后输出总人数-max(相加再减一)就好了

示例代码

def LIS(ls):
    dp = [1 for i in range(len(ls))]
    for ei,i in enumerate(ls):
        for ej,j in enumerate(ls[:ei]):
            if i>j and dp[ei]<dp[ej]+1:
                dp[ei] = dp[ej]+1
    return dp
            
cnt = int(input())
ls = [int(i) for i in input().split()]

dp1 = LIS(ls)
dp2 = LIS(ls[::-1])[::-1]

dp = [sum(i)-1 for i in zip(dp1,dp2)]

print(cnt - max(dp))