题解 | #合唱队#最长递增序列长度+最长递减序列长度-1的最大值

/*HJ24合唱团
不允许改变队列元素的先后顺序 
且 不要求最高同学左右人数必须相等
已知所有N位同学的身高，计算最少需要几位同学出列，
可以使得剩下的同学排成合唱队形。
找最长递增递减子序列*/
#include <iostream>
#include <queue>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[3000];
	int maxx=0;//合唱序列长度最大值
	vector<int>dp0(3000,1);//递增序列长度
	vector<int>dp1(3000,1);//递减序列长度
	vector<int>dp(3000,1);//合唱序列长度
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	for(int i=0;i<n;i++)//递增子序列长度 
	{
		for(int j=0;j<i;j++)
		if(a[i]>a[j]) dp0[i]=max(dp0[i],dp0[j]+1);
	}
	for(int i=n-1;i>=0;i--)//递减子序列长度 
	{
		for(int j=n-1;j>i;j--)
		if(a[i]>a[j]) dp1[i]=max(dp1[i],dp1[j]+1);
	}
	for(int i=0;i<n;i++) 
	{
		dp[i]=dp0[i]+dp1[i]-1;
		if(dp[i]>=maxx) maxx=dp[i];
//		cout<<dp0[i]<<" ";
	}	
	cout<<n-maxx<<endl;
}