Keshawn_lu's Blog

牛客网 KY73.合唱队形

字数统计: 688阅读时长: 3 min
2021/03/03 Share

题目简介:

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

输出

1
4

思路:

动态规划,枚举每个人作为中心点时的情况

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;
}
CATALOG
  1. 1. 题目简介:
  2. 2. 输入描述:
  3. 3. 输出描述:
  4. 4. 输入
  5. 5. 输出
  6. 6. 思路:
  7. 7. 代码如下: