题目描述
N位同学站成一排，音乐老师要请其中的\((N-K)\)位同学出列，使得剩下的\(K\)位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为\(1,3......,K\)，他们的身高分别为\(T_1,T_2,......,T_K\)则他们的身高满足\(T_1<T_2<...<T_{i+1}>T_i>...T1\)\((1\leq i \leq K)\)
你的任务是，已知所有\(N\)位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入输出格式
输入格式
共二行。
第一行是一个整数\((2 \leq N \leq 100)\)，表示同学的总数。
第二行有\(n\)个整数，用空格分隔，第\(i\)个整数\((130\leq i \leq 230)\)是第\(i\)位同学的身高(厘米)。
输出格式
一个整数，最少需要几位同学出列。
思路
因为我们知道这个合唱队形是一个山形，也就是在中间最高的人\(i\)左边是一个上升子序列，右边是下降子序列，又因为我们要求最少几人，即最长上升和最长下降子序列，于是代码就出来了。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=100+5;
int n,a[maxn],f[maxn],q[maxn];
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
a[0]=a[n+1]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
if(a[i]>a[j])
f[i]=max(f[i],f[j]+1); //最长上升子序列
for(int i=n;i>=1;i--)
for(int j=n+1;j>i;j--)
if(a[i]>a[j])
q[i]=max(q[i],q[j]+1);//最长下降子序列（注意：不能正着求，因为如果正着求就还需要一个循环枚举最高的人的位置）
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,f[i]+q[i]-1);//$ans$求最长的合唱队形，注意要减1
cout<<n-ans;//答案
return 0;
}