题解 | #合唱队形#

思路

关于怎么理解“峰型”队形：
以160,170,155,180,170,160为例。
对于其中的每个人，我们求两个值，分别设dp1[6] 与dp2[6]
其中dp1[i] 意为从0开始 到i为止 这前几个人的最长上升子序列长度。如，对于180的人而言，dp1[3] = 3 (也就是 160,170,180) 同理。dp2[i] 意为从i开始 到末尾为止 这后几个人的最长下降子序列长度。如，对于180的人而言，dp2[3] = 3 (也就是 180,170,160)

两个量求和，再减1（因为他自己被算了两次），得到的是“峰型”序列的长度。对180而言，该数是3+3-1=5

所有位置的峰型序列长度 最大的就是整个队伍能形成的最大峰型队列长度

则需要至少6-5 = 1 个出列

#include<iostream>
#include<cstring>
/*
合唱队形
*/
using namespace std;
const int MAXN = 1000+1;
int arr[MAXN];
int dp1[MAXN];
int dp2[MAXN];

void getUp(int n){
	//得到各个位置 以其为结尾的最大上升子序列
	for (int i = 0; i < n; ++i){
		dp1[i] = 1;
		for (int j = 0; j < i; ++j){
			if(arr[i] > arr[j]){
				dp1[i] = max(dp1[i],dp1[j] + 1);
			}
		}
	}
}

void getDown(int n){
	//得到各个位置 以其为结尾的最大上升子序列
	for (int i = n - 1; i >= 0; --i){
		dp2[i] = 1;
		for (int j = n - 1; j > i; --j){
			if(arr[i] > arr[j]){
				dp2[i] = max(dp2[i],dp2[j] + 1);
			}
		}
	}
}

int main(){
	int n;
	cin>>n;
	for (int i = 0; i < n; ++i){
		cin>>arr[i];
	}
	memset(dp1,0,sizeof(dp1));
	getUp(n);
	//得到各个位置 以其为结尾的最大上升子序列
	memset(dp2,0,sizeof(dp2));
	getDown(n);
	//得到各个位置 以其为结尾的最大上升子序列
	int maxUpDown = 1;
	//记录先上升后下降的最长序列长度
	for (int i = 0; i < n; ++i){
		maxUpDown = max(maxUpDown,dp1[i] + dp2[i] -  1);
	}
	//求剔除人数
	int res = n - maxUpDown;
	cout<<res<<endl;

	return 0;
}