題目描述:計(jì)算最少出列多少位同學(xué)，使得剩下的同學(xué)排成合唱隊(duì)形.

N位同學(xué)站成一排，音樂老師要請其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)形(不允許交換位置)。 合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號為1，2…，K，他們的身高分別為T1，T2，…，TK，則他們的身高滿足存在i（1<=i<=K）使得T1<T2<......<Ti-1<Ti>Ti+1>......>TK。你的任務(wù)是，已知所有N位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形。

輸入描述：整數(shù)N以及N位同學(xué)的身高

輸出描述：最少需要幾位同學(xué)出列

輸入例子：

8

186 186 150 200 160 130 197 200

輸出例子：

4

算法實(shí)現(xiàn)：

#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;}關(guān)鍵點(diǎn)：將問題拆分為兩部分，正向和反向最長遞增子序列組合為 合唱隊(duì)型。