<= 求赞qwq,码字不易,你的支持是我写作的动力
宣传一下算法提高课题解合集
482.合唱队形
$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$
根据题意与复杂度,很明显先尝试用 线性dp 来解决
再观察排队形的过程,明显就是和AcWing 1014.登山一样的思路
所以考虑用 最长上升(下降)子序列模型 来解决
方案:线性dp 复杂度:$O(n ^ 2)$:
状态表示
$f[i]$ 表示以第 $i$ 个位置作为当前子序列的右端点的值
$g[i]$ 表示以第 $i$ 个位置作为当前子序列的右端点的值
状态属性
$f[i]$ 求最长上升子序列的最多景点个数
$g[i]$ 求最长下降子序列的最多景点个数
状态计算
$f[i] = max(f[i], f[j] + 1) (1 \le j < i \le n)$
$g[i] = max(g[i], g[j] + 1) (1 \le i < j \le n)$
$f$ 数组的求法和 $g$ 数组很像,因为把数组 $reverse$ 后,求新数组最长上升子序列就是求原数组最长下降子序列
答案表示
在预处理出最长上升子序列和最长下降子序列后,根据每一个点来划分
稍微转化一下:$ans = 总人数 - max$(包含 $i$ 的最长上升子序列 + 包含 $i$ 的最长下降子序列)
所以 $ans = n - max(f[i] + g[i] - 1)$
变量名解释:
$n$ 是同学的总数
$x[]$:记录每个同学的身高
$f[], g[]$:见上分析
$ans$ 答案,表示最少需要几位同学出列
c++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1009;
int n, x[N]; //景点数量和景点海拔
int f[N]; //求最长上升子序列
int g[N]; //求最长下降子序列
int ans = 0;
int main()
{
cin >> n;
for(int i = 1;i <= n;++ i)
//首先求最长上升子序列
{
cin >> x[i]; f[i] = 1; //注意子序列至少有一个节点
for(int j = 1;j < i;++ j) //枚举第二个节点
if(x[i] > x[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(x[i] > x[j])
g[i] = max(g[i], g[j] + 1); //求最长下降子序列
}
for(int i = 1;i <= n;++ i)
ans = max(ans, f[i] + g[i] - 1);
cout << n - ans << endl; //与“登山”的唯一不同点
return 0;
}
ans不是组成合唱队形的最多人吗?用n-ans才是最少出队人数