这道题是一个很经典的动态规划。
因为合唱队形的身高是从低——高——低来排的，所以就可以利用分治的思想将队形分成两个部分：低——高是最长上升子序列；高——低是最长下降子序列。
这道题其实可以用二分查找来优化，可是这题n≤100，没有必要优化，需优化题详见P1020 导弹拦截。
做法详见代码
#include <bits/stdc++.h>
using namespace std;
int n,h[105],dp1[105],dp2[105],daan[105],sum=-1;//dp[i]是指以第i个数为结尾的最长上升子序列
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>h[i];//输入
}
for(int i=1;i<=n;i++)
{
dp1[i]=dp2[i]=1;//将dp1和dp2数组初始化为1
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(h[i]>h[j] and dp1[i]<=dp1[j]+1)
{
dp1[i]=dp1[j]+1;//先从低到高的过一遍
}
}
}
for(int i=n;i>1;i--)
{
for(int j=i+1;j<=n;j++)
{
if(h[i]>h[j] and dp2[i]<=dp2[j]+1)
{
dp2[i]=dp2[j]+1;//再从高到低的过一遍
}
}
}
for(int i=1;i<=n;i++)
{
daan[i]=dp1[i]+dp2[i]-1;//重要的事情说三遍，因为dp1和dp2都把最中间的数算了一遍，所以要-1，-1，-1
if(daan[i]>sum)
{
sum=daan[i];//求答案中最大的
}
}
cout<<n-sum;//因为sum是最多剩下多少同学，所以要用n-sum
return 0;
}
建议大家去做一下P1077 摆花