本文主要是介绍DP 合唱队形，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入输出格式
输入格式：
输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。
输出格式：
输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
输入输出样例
输入样例#1： 复制
8 186 186 150 200 160 130 197 220
输出样例#1： 复制
4
说明
对于50％的数据，保证有n<=20；
对于全部的数据，保证有n<=100。
题目分析：
其实是求两个最长递增序列（是递增）
我们按照从左到右和由右到左的顺序将n个同学排成数列，如何在两个数列中寻求递增的和未必连续的最长子序列成为关键。
a为身高序列。
b为从左到右身高递增的人数序列，其中b[i]为同学1到同学i身高之间满足递增顺序的最大人数（包括i）。
c为从右到左身高递增的人数序列，其中c[i]为同学n到同学i身高之间满足递增顺序的最大人数（包括i）。
要使b[i]和c[i]最大，子问题的解b[j].c[k]必须最大，（1<=j<=i-1,i+1<=k<=n）
出列人数则为n-max（b[i]+c[i]）+1（i同学被重复计算，因此需要加1）
实现细节：
b和c求得相当于最长递增序列，不是最长不下降序列
代码实现：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int a[maxn],i,j,k,maxx,c[maxn],b[maxn];
int main()
{int n;cin>>n;for(i=1;i<=n;i++){b[i]=1;c[i]=1;cin>>a[i];}for(i=1;i<=n;i++) {maxx=0;for(j=1;j<=i-1;j++)if(a[j]<a[i]&&b[j]>maxx)maxx=b[j];if(maxx>0){b[i]=maxx+1;}}for(i=n;i>=1;i--){maxx=0;for(j=i+1;j<=n;j++)if(a[j]<a[i]&&c[j]>maxx)maxx=c[j];if(maxx>0){c[i]=maxx+1;}}maxx=0;for(i=1;i<=n;i++)maxx=max(maxx,b[i]+c[i]);cout<<n-maxx+1<<endl;return 0;
}#include<bits/stdc++.h>
using namespace std;
int main()
{int i,j,n,a[200],b[200],c[200];cin>>n;for(i=0;i<n;i++)cin>>a[i];memset(b,0,sizeof(b));memset(c,0,sizeof(c));for(i=0;i<n;i++){b[i]=1;for(j=0;j<=i-1;j++){if(a[i]>a[j]&&b[j]+1>b[i]){b[i]=b[j]+1;}}}for(i=n-1;i>=0;i--){c[i]=1;for(j=i+1;j<n;j++){if(a[i]>a[j])c[i]=c[j]+1;}}int max=0;for(i=0;i<n;i++)if(b[i]+c[i]>max)max=b[i]+c[i];cout<<n-max+1<<endl;return 0;}
这篇关于DP 合唱队形的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
