题目简介:
N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学不交换位置就能排成合唱队形。 合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1, 2, …, K,他们的身高分别为T1, T2, …, TK, 则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。 你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
输入描述:
1 2
| 输入的第一行是一个整数N(2 <= N <= 100),表示同学的总数。 第一行有n个整数,用空格分隔,第i个整数Ti(130 <= Ti <= 230)是第i位同学的身高(厘米)。
|
输出描述:
1 2
| 可能包括多组测试数据,对于每组数据, 输出包括一行,这一行只包含一个整数,就是最少需要几位同学出列。
|
输入
1 2
| 8 186 186 150 200 160 130 197 220
|
输出
思路:
动态规划,枚举每个人作为中心点时的情况
dp_asc[i]
代表以i
作为中心点时,左边升序的最大人数
dp_dsc[i]
代表以i
作为中心点时,右边降序的最大人数
然后可以得到每个人作为中心点的最大人数的最大值,再用总人数去减,便可得到结果。
按左边升序为例,首先初始化dp_asc[i] = 1
(即自身一个人),若在循环中students[i] > students[j]
,则更新dp_asc[i] = max(dp_asc[i], dp_asc[j] + 1)
。
tips:
- 左边升序时需从前往后递推
- 右边降序时需从后往前递推
代码如下:
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 41 42 43 44 45 46 47 48 49 50
| #include <iostream> #include <string> #include <vector> #include <algorithm> #include <unordered_map> #include <cmath> #include <iomanip> #include <set> #include <map>
using namespace std;
int main() { int N; cin >> N;
vector<int> students(N); for (int i = 0; i < N; i++) cin >> students[i];
vector<int> dp_asc(N); vector<int> dp_dsc(N);
for (int i = 0; i < N; i++) {
dp_asc[i] = 1; for (int j = 0; j < i; j++) {
if (students[i] > students[j]) dp_asc[i] = max(dp_asc[i], dp_asc[j] + 1); } }
for (int i = N - 1; i >= 0; i--) {
dp_dsc[i] = 1; for (int j = N - 1; j > i; j--) {
if (students[i] > students[j]) dp_dsc[i] = max(dp_dsc[i], dp_dsc[j] + 1); } }
int max_num = 0; for (int i = 0; i < N; i++) max_num = max(max_num, dp_asc[i] + dp_dsc[i] - 1);
cout << N - max_num << endl; }
|