分析

首先,要让最少的同学出列,就等价于让尽量多的同学留在队伍中。
观察到合唱队形满足 ,在合唱队形中,以第 个同学为分界点(分界点即为最高点),从 递增,从 递减。
设原队形中第 个同学的身高为 。假设我们选取第 个同学作为合唱队形的最高点,那么要使尽量多的同学留在队伍中,合唱队形左边应该是 数组中从左到右以 结尾的 ;右边应该是 数组中从右到左以 结尾的的
我们可以预处理出 数组中正向和逆向的最长上升子序列长度,然后枚举合唱队形的最高点,就可以得到最多能有多少同学留在队伍中,也就能知道最少需要几位同学出列。
为从左到右以 结尾的 长度, 为从右到左以 为结尾的 长度。
有状态转移方程


当以 为最高点时,能留在队伍中的同学个数为
因此,答案为

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#define N 103
using namespace std;
int l[N],r[N];
int height[N];
int n,ans=0x3f3f3f3f;
int main()
{
    int i;
    cin>>n;
    for(i=1;i<=n;i++) scanf("%d",height+i);
    for(i=1;i<=n;i++) l[i]=r[i]=1;//LIS初始长度都为1
    int j;
    //计算两个方向的LIS长度
    for(i=2;i<=n;i++)
    {
        for(j=1;j<i;j++)
        {
            if(height[i]>height[j])
            {
                l[i]=max(l[i],l[j]+1);
            }
        }
    }
    for(i=n-1;i>=1;i--)
    {
        for(j=n;j>i;j--)
        {
            if(height[i]>height[j])
            {
                r[i]=max(r[i],r[j]+1);
            }
        }
    }
    //迭代更新最小值
    for(i=1;i<=n;i++) ans=min(ans,n-(l[i]+r[i]-1));
    cout<<ans<<endl;
    return 0;
}