题目大意

给定长度为 N 的序列 a ，求构造以 a[i] 为最大值，左边递增，右边递减，这样的序列，所需要删去数的个数的最小值

分析

题意已经非常明显了吧
我们要求一个先上升后下降的序列，那么转折点是关键
可以发现，转折点前的序列要求上升，转折点后的序列（如果反着看）也要求上升
那么所求 = 总人数 - 上升序列人数

所以直接枚举转折点，正反跑两遍 LIS 不就完事了吗

代码

#include<bits/stdc++.h>
using namespace std;

const int N=110;

int n,ans=N;
int a[N],f[N],l[N],r[N];
//l[i] 表示以 i 为转折点 0~i 符合合唱队形 所删的最少人数。 r 类似。 

int main()
{
    scanf("%d",&n);

    for(int i=1;i<=n;++i) scanf("%d",&a[i]); 

    f[1]=a[1];
    int point=1;

    for(int i=2;i<=n;++i)
    {
        if(a[i]>f[point]) f[++point]=a[i];
        else
        {
            int x=lower_bound(f+1,f+point+1,a[i])-f;
            f[x]=a[i];
        }
        l[i]=i-point;
        //i 是总人数，point 是升序人数 
    }

    memset(f,0,sizeof(f));
    f[1]=a[n];
    point=1;

    for(int i=n-1;i>=1;--i)
    {
        if(a[i]>f[point]) f[++point]=a[i];
        else
        {
            int x=lower_bound(f+1,f+point+1,a[i])-f;
            f[x]=a[i];
        }
        r[i]=n-i+1-point;
    }

    for(int i=1;i<=n;i++) ans=min(ans,l[i]+r[i]);

    printf("%d",ans);

    return 0;
}