$N$ 位同学站成一排,音乐老师要请其中的 $(N-K)$ 位同学出列,使得剩下的 $K$ 位同学排成合唱队形。
合唱队形是指这样的一种队形:设 $K$ 位同学从左到右依次编号为 $1,2…,K$,他们的身高分别为 $T_1,T_2,…,T_K$, 则他们的身高满足 $T_1 < … < T_i > T_{i+1} > … > T_K(1 \\le i \\le K)$。
你的任务是,已知所有 $N$ 位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
输入格式
输入的第一行是一个整数 $N$,表示同学的总数。
第二行有 $N$ 个整数,用空格分隔,第 $i$ 个整数 $T_i$ 是第 $i$ 位同学的身高(厘米)。
输出格式
输出包括一行,这一行只包含一个整数,就是最少需要几位同学出列。
数据范围
$2 \\le N \\le 100$,
$130 \\le T_i \\le 230$
输入样例:
8
186 186 150 200 160 130 197 220
输出样例:
4
算法1
(动态规划) $O(n^2)$
合唱队形是指这样的一种队形:设 $K$ 位同学从左到右依次编号为 $1,2…,K$,他们的身高分别为 $T_1,T_2,…,T_K$, 则他们的身高满足 $T_1 < … < T_i > T_{i+1} > … > T_K(1 \\le i \\le K)$。
可以发现合唱队型指的就是,$1$ 到 $i$ 为最长上升子序列,$i$ 到 $n$ 为最长下降子序列。
发现和 登山 一题类似,我们可以用此方法求出 $i$ 的位置及最长的合唱队型的人数。
最终注意我们求出的 $res$ 是 最长的合唱队型的人数,而题目中问的是 需要剔除的人数,我们答案需要输出 $n - res$。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
int n;
int h[N];
int f[N],g[N];
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i ++) scanf("%d",&h[i]);
for(int i = 1;i <= n;i ++){
f[i] = 1;
for(int j = 1;j <= i;j ++){
if(h[i] > h[j]) f[i] = max(f[i],f[j] + 1);
}
}
for(int i = n;i >= 1;i --){
g[i] = 1;
for(int j = n;j >= i;j --){
if(h[i] > h[j]) g[i] = max(g[i],g[j] + 1);
}
}
int res = 0;
for(int i = 1;i <= n;i ++) res = max(res,f[i] + g[i] - 1);
printf("%d\n",n - res);
return 0;
}