合唱团（牛客）

题目描述：

计算最少出列多少位同学，使得剩下的同学排成合唱队形

说明：

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

解题思路：（来自谢小橙）

1. 对于题目，我个人理解是所有人都已经站好位，不能再改变位置了，只能从当中去掉人组成合唱队。同时，可以考虑中间的人两边没有人的情况（比如两头的两个人，或者这个人太矮周围的人都比他高的情况），但是这种情况基本被pass掉。    
2. 对于最长递增子序列：比如题中所给出的示例：186 186 150 200 160 130 197 200，先看每个人的左边可能出现最多的人。首先如果第一个数186在中间，左边没有数，就自己一个人，所以是1；第二个数186因为左边那个人跟他一边高，没有比他矮的了，所以也是1；第三个数150，左边的人都比他高，他如果是中间的话左边也他自己一个人，所以还是1；第四个数200，因为不能换位置，所以只能留186或者150，加上自己，就是2...最后再以197为例，左边保留150,160是左边人最多的情况，再加上自己，就是3。所以每个人左边人做多的情况（加上自己）就是（186）1 1 1 2 2 1 3 4（200）。
同理最长递减子序列：看一下每个人右边可能出现最多的人，这时我们从后往前看。200在最右面，所以自己一个人，是1；197最右面没有比他矮的，自己，是1...160左边一个比他矮的，所以算上自己是2，以此类推。所以每个人右边人做多的情况（加上自己）就是（186）3 3 2 3 2 1 1 1（200）     

3. 所以将上面最长递增和最长递减子序列的对应相加，就可以得到自己如果是中间的那个人，可以得到的最大的合唱队人数。当然，自己加了两遍，所以得减掉一个自己。

4.题目问的是最少去掉的人，所以最后的结果：    总人数 - 该数所在队列人数 = 需要出队的人数

最长递增子序列：（来自w8ed）

• 定义如下符号

  n表示问题序列的总长度

  A[ 1：n ] 表示下标从1到 n 的一个问题序列，A[ i ]表示问题序列A[ 1：n ]中的第i个元素

  L[ 1 : n ]中的L~i~表示以A~i~结尾的最长递增子序列的长度

• 由于问题的最优解必然对应着某个子序列，而这个子序列又必然由某个A~i~结尾，因此，由所有A~i~结尾的最长递增子序列的长度L~i~，构成了问题的解空间。max(L~i~)就是最优解
• 求解L~i~的递归方程如下：

   

注意事项：

vector容器的就地逆置

#include<algorithm>
using namespace std;

int N;
cin >> N;
vector<int> Lds(N,1);  //设置长度为N，并且初试值全为1

reverse(Lds.begin(),Lds.end()); //实现就地逆置

 

AC代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void  getLcs(vector<int> height, vector<int> &Lcs)
{
	for(int i=0; i<height.size(); i++){
		int max = 0; 
		for(int j=0; j<i; j++){
			if( height[j]<height[i]&&Lcs[j]>max ){
				max = Lcs[j];
			}
		}
		Lcs[i] = max+1;
	}
} 

int main()
{
	int N; //总共有多少个人
	
	while( cin>>N ){
		vector<int> height(N);
		vector<int> Lcs(N);  //最长递增子序列 
		vector<int> Lds(N);  //最长递减子序列 
		
		for(int i=0; i<N; i++){
			cin >> height[i];
		}
		
		getLcs(height,Lcs);
		reverse(height.begin(),height.end());
		getLcs(height,Lds);
		reverse(Lds.begin(),Lds.end());
		
		int max = -1;
		for(int i=0; i<height.size(); i++){
			if( Lcs[i]+Lds[i]-1 > max ){
				max = Lcs[i]+Lds[i]-1;
			}
		}
		
		cout<<N-max<<endl;
	} 
	
	return 0;
}