P1091 [NOIP2004 提高组] 合唱队形

 题目

P1091 [NOIP2004 提高组] 合唱队形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 

题解：

1.最少需要几位同学出列---->最多能留下多少同学---->遍历所以同学，以每个同学为中心，求其最长的递增序列和最长的递减序列之和 ---->选出最大的和。

2.某个同学的身高是否能与之前或者之后的同学身高形成递增或者递减，不能单纯比较该同学身高与前后同学身高的大小关系，而是要在前后同学能够形成递增或者递减的基础上，观察能否在此基础上继续叠加。（与递归的思想有点相似）

 代码：

#include
#include
#include
using namespace std;
const int N = 101;
int a[N], l[N], r[N];
int main()
{
	int n, i, j;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (i = 1; i <= n; i++) {
		l[i] = 1;
		for (j = 1; j < i; j++) {
			if (a[i] > a[j])
				l[i] = max(l[i], l[j] + 1);
		}
	}
	for (i = n; i >= 1; i--) {
		r[i] = 1;
		for (j = i + 1; j <= n; j++) {
			if (a[i] > a[j])
				r[i] = max(r[i], r[j] + 1);
		}
	}
	int maxn = 0;
	for (i = 1; i <= n; i++) maxn = max(maxn, l[i] + r[i] - 1);
	cout << n - maxn;
}