建设官网站电脑软件推广平台

概览检索
动态规划DP 最长上升子序列模型

合唱队形

原题链接

AcWiing 482. 合唱队形

题目描述

N位同学站成一排，音乐老师要请其中的 (N−K)位同学出列，使得剩下的 K位同学排成合唱队形。

合唱队形是指这样的一种队形：设 K位同学从左到右依次编号为 1，2…，K，他们的身高分别为 T1，T2，…，TK，
则他们的身高满足 T1<…Ti+1>…>TK(1≤i≤K)。

你的任务是，已知所有 N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入格式
输入的第一行是一个整数 N，表示同学的总数。
第二行有 N个整数，用空格分隔，第 i个整数 Ti是第 i 位同学的身高(厘米)。

输出格式
输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

数据范围
2≤N≤100,130≤Ti≤230

输入样例：

8
186 186 150 200 160 130 197 220

输出样例：

4

题目分析

由合唱队形满足的要求 身高满足 T1<…Ti+1>…>TK 可知该队形就是一个先上升后下降的子序列；
最少去掉的同学 即使合唱队形中的人数最多。
由此联想到 登山（点击链接跳转题目）。
也可参考 怪盗基德的滑翔伞（点击链接跳转题目）。

以最高的同学为划分，划分为左半部分的递增子序列，和右半部分的递减子序列（也就是相当于逆着的递增子序列），可直接看出该题为最长上升子序列模型。
分别求出左半部分和右半部分在以不同同学为那个顶峰时的值，分别存储在 f[i], g[i] 中。
则对应一个顶峰同学为i的合唱队形下的人数为 f[i]+g[i]-1 ，
遍历所有1~n的可能情形下，取其中人数最多（数值最大）的值max，
则出列的最少同学的数目为总人数n 减去该最大值max。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=110;
int n;
int a[N],f[N],g[N];
int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);//左半部分递增子序列for(int i=1;i<=n;i++){f[i]=1;  //序列中只有a[i]，长度为1//前一个数为a[j]for(int j=1;j<i;j++)if(a[j]<a[i])  //满足前一个数a[j]大于后一个数a[i]f[i]=max(f[i],f[j]+1);  //尝试更新，f[j]+1为以前一个数a[j]结尾的最长序列的长度f[j]再加上当前最有一个数a[i]（长度为1）}//右半部分递减子序列for(int i=n;i>=1;i--){g[i]=1;for(int j=n;j>i;j--)if(a[j]<a[i])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-res);  //所有人数-最大值return 0;
}