题目要求: N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1, 2, …, K,他们的身高分别为T1, T2, …, TK,则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1≤i≤K)。 你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。 输入 输入有多行,第一行是一个整数N(2 ≤ N ≤ 100),表示同学的总数。第二行有n个整数,用空格分隔,第i个整数Ti(100 ≤ Ti ≤ 300)是第i位同学的身高(厘米)。 输出 输出只有一行,这一行只包含一个整数,就是最少需要几位同学出列。 样例输入 8 186 186 150 200 160 130 197 220 样例输出 4
解题思路: 分别对数组正向反向求出两个最长上升子序列,枚举两个子序列中的每个位置为最高点,计算两个子序列之和 - 1即为以当前位置为最高点的站队的最多人数,枚举所有位置,取最大值,用总数减去即为应当出列的人数。
通关代码:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> getLIS(vector<int> arr) {
int LEN = arr.size();
vector<int> dp(101);
for (int i = 0; i < LEN; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return dp;
}
int main() {
vector<int> arr;
vector<int> lAdd;
vector<int> rAdd;
int n, value, result = 1;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> value;
arr.emplace_back(value);
}
lAdd = getLIS(arr);
reverse(arr.begin(), arr.end());
rAdd = getLIS(arr);
for (int i = 0; i < n; i++) {
result = max((lAdd[i] + rAdd[n - i] - 1), result);
}
cout << n - result;
return 0;
}
通关截图: