华为OJ合唱队

快来打我* 2022-09-30 06:07 207阅读 0赞

描述

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

说明：

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。  
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足存在i（1<=i<=K）使得

Ti < T2 < ...< Ti-1 < Ti > Ti+1>...>TK

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

知识点  
循环  
运行时间限制  
0M  
内存限制  
0

输入  
整数N  
一行整数，空格隔开，N位同学身高

输出  
最少需要几位同学出列  
样例输入  
8 186 186 150 200 160 130 197 200  
样例输出  
4

## 求最长上升子序列 ##

现在有一个序列，要求他的最长上升子序列。直观上并不是很好求得，反过来看的话就能比较好理解：  
现在对于总序列里的第i个元素来说，包含元素i的最长子序列是多少呢？如果i前面有能构成最长上升序列的（设它为j），而且i数值比j大，那很显然到第i个元素(包含元素i)的最长子序列是到第j个元素的最长子序列+1；否则到第i个元素(包含元素i)的最长子序列就是是1。因为前面没有比他更小的了，只有自身构成一个子序列。

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    //最长升序
    void GetUpSeries(vector<int> src, vector<int>& dst)
    {
    	int N = src.size();
    	dst.resize(N);
    	for (int i = 0; i < N; i++)
    	{
    		dst[i] = 1;
    	}
    
    	for (int i = 0; i < N; i++)
    	{
    		for (int j = 0; j < i; j++)
    		{
    			if (src[j]<src[i] && dst[j] + 1>dst[i])
    			{
    				dst[i] = dst[j] + 1;
    			}
    		}
    	}
    }
    
    //最长降序
    void GetDownSeries(vector<int> src, vector<int>& dst)
    {
    	int N = src.size();
    	dst.resize(N);
    	for (int i = 0; i < N; i++)
    	{
    		dst[i] = 1;
    	}
    
    	for (int i = N-1; i >=0; i--)
    	{
    		for (int j = N-1; j > i; j--)
    		{
    			if (src[j]<src[i] && dst[j] + 1>dst[i])
    			{
    				dst[i] = dst[j] + 1;
    			}
    		}
    	}
    }
    
    //动态规划，dst记录升序或降序元素个数,初始值为1
    int main(void)
    {
    	int N;
    	cin >> N;
    
    	vector<int> src;
    	vector<int> dst1;
    	vector<int> dst2;
    	for (int i = 0; i < N; i++)
    	{
    		int tmp;
    		cin >> tmp;
    		src.push_back(tmp);
    	}
    
    	GetUpSeries(src, dst1);
    	GetDownSeries(src, dst2);
    	
    	int max = 0;
    	for (int i = 0; i < N;i++)
    	{
    		if (dst1[i] + dst2[i] > max)
    		{
    			max = dst1[i] + dst2[i];
    		}
    	}
    
    	cout << N - max + 1;
    	return 0;
    }