NC16664 合唱队形

分析

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

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

代码

#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;
}