N位同学站成一排,音乐老师要请其中的(N−K)位同学出列使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2,…,K,他们的身高分别T1,T2,…,TK,则他们的身高满足T1<T2<…<Ti,Ti>Ti+1>…>TK(1≤i≤K) <t2<…<ti,ti>。
<t2<…<ti,ti>你的任务是，已知所有
N 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入的第一行是一个整数
N（2≤N≤100),表示同学的总数。第二行有n个整数，用空格分隔，第
i 个整数Ti(130≤Ti≤230)是第i位同学的身高（厘米）。
输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
对于50%的数据，保证有n ≤ 20；对于全部的数据，保证有n≤100。
今天为大家带来一道经典线性dp题-----合唱队形的题解，再看这篇题解之前小编建议先去看一下------最长上升子序列这道题（此题是很多线性dp题目的基础）
其实读完题目，我们便可知此题无疑于在合唱队中做了一次寻找最长上升子序列与一次最长下降子序列。即一次正向寻找最长上升子序列，与一次反向寻找最长上升子序列的操作。
分别用数组记录下以其为终点的最长上升子序列与最长下降子序列的长度。此时，万事俱全只欠找出其转折点“i”的位置，也就是个子最高，抛物线顶点的人。而找出其位置只需用循环来遍历存储下的每个点的最长上升子序列与最长下降子序列的长度，在遍历循环中“打个擂台”，求出最长上升子序列与最长下降子序列的长度和最大的点以“t”记录其下标即可。输出：
由于问题为最少需几位同学出列，只需用（总人数n）-(以第t个人结尾的最长上升子序列的长度)-（以第t个人结尾的最长下降子序列的长度）+1即可求出答案。
tips:为何答案要加1呢，因为在最后相减时第t个人的长度被减了两遍，需加回1才可得出正解。
#include<iostream>
using namespace std;
int main()
{
int n,a[105],f[3][105],i,j;//关于二维数组f，其行坐标为零时记录以此点为终点的最长上升子序列的长度，而为一时记录以其为终点的最长下降子序列的长度。
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i];
f[0][i]=1;
f[1][i]=1;
}//输入，并将f数组初始化为最长上升子序列与最长下降子序列长度为1
for(i=1;i<=n;i++)
{
for(j=1;j<i;j++)
{
if(a[i]>a[j])
{
f[0][i]=max(f[0][i],f[0][j]+1);
}
}
}//正向求其最长上升子序列长度，并存入f[0][i]中
for(i=n;i>=1;i--)
{
for(j=n;j>i;j--)
{
if(a[i]>a[j])
{
f[1][i]=max(f[1][i],f[1][j]+1);
}
}
}//反向求其最长上升子序列长度（即求最长下降子序列长度），并存入f[1][i]中
int max=0,t=0;
for(i=1;i<=n;i++)
{
if(max<f[0][i]+f[1][i])
{
max=f[0][i]+f[1][i];
t=i;
}
}//“打擂台”，求最高人的下标，计入“t”变量中
cout<<n-f[0][t]-f[1][t]+1;//简单的输出，注意加一哦
return 0;//完美结束
}
原文：https://www.cnblogs.com/tcwbob/p/13400028.html