网站认证要钱,南通网站的优化,完整的app网站开发,成都网站seo设计概览检索 动态规划DP 最长上升子序列模型 合唱队形
原题链接
AcWiing 482. 合唱队形
题目描述
N位同学站成一排#xff0c;音乐老师要请其中的 (N−K)位同学出列#xff0c;使得剩下的 K位同学排成合唱队形。
合唱队形是指这样的一种队形#xff1a;设 K位同学从左到右… 概览检索 动态规划DP 最长上升子序列模型 合唱队形
原题链接
AcWiing 482. 合唱队形
题目描述
N位同学站成一排音乐老师要请其中的 (N−K)位同学出列使得剩下的 K位同学排成合唱队形。
合唱队形是指这样的一种队形设 K位同学从左到右依次编号为 12…K他们的身高分别为 T1T2…TK 则他们的身高满足 T1…Ti1…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…Ti1…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 N110;
int n;
int a[N],f[N],g[N];
int main(){scanf(%d,n);for(int i1;in;i) scanf(%d,a[i]);//左半部分递增子序列for(int i1;in;i){f[i]1; //序列中只有a[i]长度为1//前一个数为a[j]for(int j1;ji;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 in;i1;i--){g[i]1;for(int jn;ji;j--)if(a[j]a[i])g[i]max(g[i],g[j]1);}int res0;for(int i1;in;i) resmax(res,f[i]g[i]-1); //取和的最大值printf(%d,n-res); //所有人数-最大值return 0;
}
