[NOIP2004 提高组] 合唱队形

题目描述

$n$ 位同学站成一排，音乐老师要请其中的 $n-k$ 位同学出列，使得剩下的 $k$ 位同学排成合唱队形。

合唱队形是指这样的一种队形：设 $k$ 位同学从左到右依次编号为 $1,2,$ … $,k$，他们的身高分别为 $t_1,t_2,$ … $,t_k$，则他们的身高满足 $t_1< \cdots <t_i>t_{i+1}>$ … $>t_k(1\le i\le k)$。

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

输入格式

共二行。

第一行是一个整数 $n$（$2\le n\le100$），表示同学的总数。

第二行有 $n$ 个整数，用空格分隔，第 $i$ 个整数 $t_i$（$130\le t_i\le230$）是第 $i$ 位同学的身高（厘米）。

输出格式

一个整数，最少需要几位同学出列。

样例 #1

样例输入 #1

8
186 186 150 200 160 130 197 220

样例输出 #1

4

提示

对于 $50%$ 的数据，保证有 $n \le 20$。

对于全部的数据，保证有 $n \le 100$。

算法1

(动态规划)

1.状态定义

f[i]: 包括我，我左边比我矮的人数
g[i]: 包括我，我右边比我爱的人数

2.状态计算

(1) 从左往右扫描，枚举每一个位置，看我左边有多少个数比我小

(2) 从右往左扫描，枚举每一个位置，看我右边有多少个数比我小

(3)统计每个位置作为中间点时，剩余的人数；

(4)取最大人数 ，最后答案为 n - ans;

也就是说，剩余的人越多，出列的人越少

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int n;
int a[N];
int f[N],g[N],s[N],ans;

int main() {
	scanf("%d",&n);
	for(int i = 1; i <= n; i++) {
		scanf("%d",&a[i]);
		f[i] = 1;
		g[i] = 1;
	}

	for(int i = 2; i <= n; i++) {
		for(int j = 1; j < i; j ++) {
			if(a[i] > a[j] && f[i] <= f[j] + 1)
				f[i] = f[j] + 1;
		}
	}

	for(int i = n - 1; i >= 1; i--) {
		for(int j = i + 1; j <= n; j++) {
			if(a[i] > a[j] && g[i] <= g[j] + 1)
				g[i] = g[j] + 1;
		}
	}

	for(int i = 1; i <= n; i++) {
		s[i] = g[i] + f[i] - 1;
		if(s[i] > ans) ans = s[i];
	}
	printf("%d" ,n - ans);
	return 0;
}