【题解】「NOIP2004」合唱队形（DP，最长不下降子序列）

本文主要是介绍【题解】「NOIP2004」合唱队形（DP，最长不下降子序列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

【题目描述】
$N$位同学站成一排，音乐老师要请其中的$(N-K)$位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为$1，2\dots ，K$，他们的身高分别为$T_1，T_2，\dots ，T_K$， 则他们的身高满足$T_1<...<T_i>T_{i+1}>\dots >T_K(1<=i<=K)$。
你的任务是，已知所有$N$位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
【输入】
第一行是一个整数$N(2<=N<=100)$，表示同学的总数。第一行有$n$个整数，用空格分隔，第$i$个整数$T_i(130<=T_i<=230)$是第$i$位同学的身高(厘米)。
【输出】
一行只包含一个整数，就是最少需要几位同学出列。
【样例输入】

8
186 186 150 200 160 130 197 220

【样例输出】

4

【数据范围】
对于$50％$的数据，保证有$n<=20$； 对于全部的数据，保证有$n<=100$。

算法分析

根据题意，最后找出的同学身高的队形就是一个三角形。中间有一个同学身高最高，往左、往后身高依次递减。
假设最高是第$x$位同学，则左边到x需要找一个最长不下降子序列，右边需要找一个最长不上升子序列。
定义数组$dp1[i]$，表示以$i$为结尾的最长不下降子序列；
定义数组$dp2[i]$，表示以$i$为开头的最长不上升子序列。
因此，可以枚举中间同学的编号$x$，找出左边的最长不下降子序列，右边的最长不上升子序列，满足要求的人数就是：$dp1[x]+dp2[x]-1$（自身多加了一次，$-1$）.
最后的答案就是$n-max${ $dp1[x]+dp2[x]-1$ } $(1<=x<=n)$
时间复杂度：$O(n^3)$

参考程序

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int a[110],dp1[110],dp2[100];
int main()
{int n,mid,ans=0,mx;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)	//中间最高的人是i{			for(int j=1;j<=i;j++)	//左边最长不下降子序列{mx=0;for(int k=1;k<j;k++){if(a[k]<a[j]){if(dp1[k]>mx)mx=dp1[k];}}dp1[j]=mx+1;}for(int j=n;j>=i;j--)	//右边最长不上升子序列{mx=0;for(int k=n;k>j;k--){if(a[k]<a[j]){if(dp2[k]>mx)mx=dp2[k];}}dp2[j]=mx+1;}//那么中间人最高的为i时，满足要求的人数是左边s人，右边dp[i]人，自身算了两次，-1ans=max(ans,dp1[i]+dp2[i]-1);}cout<<n-ans<<endl;return 0;
}

这篇关于【题解】「NOIP2004」合唱队形（DP，最长不下降子序列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---