[华为OJ--C++]090-合唱队

题目描述:计算最少出列多少位同学，使得剩下的同学排成合唱队形.

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形(不允许交换位置)。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足存在i（1<=i<=K）使得T1<T2<......<Ti-1<Ti>Ti+1>......>TK。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入描述：整数N以及N位同学的身高

输出描述：最少需要几位同学出列

输入例子：

8

186 186 150 200 160 130 197 200

输出例子：

4

算法实现：

#include<iostream>#include<vector>using namespace std;/************************************************  * Author: 赵志乾  * Date: 2017-2-17   * Declaration: All Rigths Reserved !!!  ***********************************************/ int main(){	int num;	cin>>num;	vector<int>temp(num,0);	for(int i=0;i<num;i++)		cin>>temp[i];	vector<int>ret1(num,1);					//从左向右，最长顺序递增子序列	for(int i=1;i<num;i++)	{		int maxlen=1;		for(int j=i-1;j>=0;j--)			if(temp[j]<temp[i]&&maxlen<ret1[j]+1)				maxlen=ret1[j]+1;		ret1[i]=maxlen;	}	vector<int>ret2(num,1);					//从右向左，最长顺序递增子序列	for(int i=num-2;i>=0;i--)	{		int maxlen=1;		for(int j=i+1;j<num;j++)			if(temp[j]<temp[i]&&maxlen<ret2[j]+1)				maxlen=ret2[j]+1;		ret2[i]=maxlen;	}	int maxlen=0;	for(int i=0;i<num;i++)		if(maxlen<ret1[i]+ret2[i])			maxlen=ret1[i]+ret2[i];	cout<<num+1-maxlen<<endl;	return 0;}关键点：将问题拆分为两部分，正向和反向最长递增子序列组合为 合唱队型。