P1091 [NOIP2004 提高组] 合唱队形

本题链接：P1091 [NOIP2004 提高组] 合唱队形

本博客给出本题截图：

AC代码

代码解释：看成一个上升子序列 + 一个下降子序列，f[i]表示以i为结尾的最长上升子序列，g[i]表示以i为开头的最长下降自序列，本题问最少需要几名同学出列，其实就是问出列后队伍最长是多长，即我们需要求一个上升子序列和一个下降子序列，使得这两个子序列的长度和最长，即求max(f[i] + g[i] - 1)，-1的原因是因为i这个位置算了两次，然后就变成了一个简单的 LIS问题.

代码*：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int f[N], g[N];
int n;
int h[N];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i ++ ) cin >> h[i];
	
	for (int i = 1; i <= n; i ++ ) 
	{
		f[i] = 1;
		for (int j = 1; j < i; j ++ )
			if (h[j] < h[i])
				f[i] = max(f[i], f[j] + 1);
	}
	
	for (int i = n; i; i -- )
	{
		g[i] = 1;
		for (int j = n; j > i; j -- )
			if (h[j] < h[i])
				g[i] = max(g[i], g[j] + 1);
	}
	
	int res = 0;
	for (int i = 1; i <= n; i ++ )
		res = max(res, f[i] + g[i] - 1);
		
	cout << n - res << endl;
	
	return 0;
}

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
 

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/119875092