合唱队形（动态规划）

谁借莪１个温暖的怀抱￠ 2022-06-08 09:56 199阅读 0赞

### 【例9.8】合唱队形 ###

时间限制: 1000 ms 内存限制: 65536 KB

### 【题目描述】 ###

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

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

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

### 【输入】 ###

输入的第一行是一个整数N（2 ≤ N ≤ 100），表示同学的总数。第二行有n个整数，用空格分隔，第i个整数Ti（130 ≤ Ti ≤ 230）是第i位同学的身高（厘米）。

### 【输出】 ###

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

### 【输入样例】 ###

8
    186 186 150 200 160 130 197 220

### 【输出样例】 ###

### 【提示】 ###

对于50%的数据，保证有n ≤ 20；对于全部的数据，保证有n≤100。

### 【解析】； ###

![20170921210740666][]

#include<iostream>
    #include<cstring>
    #define MAXN 100
    using namespace std;
    int c[MAXN+10];//存储身高 
    int a[MAXN+10];//a[i]从左往右前i个数的最长上升序列长度
    int b[MAXN+10];//b[i]从右往左前i个数的最长上升序列长度
    int f[MAXN+10];//f[i]前i个数的最长合唱队形长度 
    int main()
    {
    	memset(a,0,sizeof(a));
    	memset(b,0,sizeof(b));
    	memset(c,0,sizeof(c));
    	memset(f,0,sizeof(f));
    	int n,i,j; 
    	cin>>n;
    	for(i=1;i<=n;i++)
    	{
    		cin>>c[i];
    		a[i]=b[i]=1;//初始状态 
    	}
    	for(i=2;i<=n;i++)//从左往右求最长上升序列 
    	{
    		for(j=1;j<i;j++)
    		{
    			if(c[i]>c[j])
    			{
    				a[i]=max(a[i],a[j]+1);
    			}
    		}
    	}
    	for(i=n-1;i>=1;i--)//从右往左求最长上升序列 
    	{
    		for(j=i+1;j<=n;j++)
    		{
    			if(c[i]>c[j])
    			{
    				b[i]=max(b[i],b[j]+1);
    			}
    		}
    	} 
    	int maxn=0;//maxn要初始化为0 
    	for(i=1;i<=n;i++)//合唱队形的最长上升序列 
    	{
    		f[i]=a[i]+b[i]-1;
    		if(maxn<f[i]) maxn=f[i];
    	}
    	cout<<n-maxn<<endl;
    	return 0;
    }

错误的代码（没找到错误的地方，后面更新）

#include<cstdio>
    #include<iostream>
    using namespace std;
    int max1=0,k = 0;
    int f1[105],f2[105],a[105];
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	for(int i = 1; i <= n; ++i)
    	{
    		scanf("%d",&a[i]);
    		f1[i] = f2[i] = 1;
    	}
    	
    	for(int i = 2; i <= n; ++i)
    	{
    	//	f1[i] = 1;
    		for(int j = 1; j < i; ++j)
    		{
    			if(a[i] > a[j])//上升 
    				f1[i] = max(f1[i],f1[j]+1);
    		}
    	 } 
    	 
    	 for(int i = n-1; i >= 1; --i)
    	 {
    	 	f2[i] = 1;
    	 	for(int j = i+1; j <= n; ++j)
    	 	{
    	 		if(a[i] > a[j])//上升 
    	 			f2[i] = max(f2[i],f2[j]+1);
    		 }
    	 }
    	 /*输出结果 
    	for(int i = 1; i <= n; ++i)
    	{
    		printf("%d ",f1[i]);
    	}
    	printf("\n");
    	for(int i = 1; i <= n; ++i)
    	{
    		printf("%d ",f2[i]);
    	}
    	printf("\n");
    	*/
    	for(int i = 1; i <= n; ++i)
    	{
    		k = f1[i] + f2[i] - 1;
    		if(k > max1) max1=k;
    	}
    	printf("%d",n-k);
    	return 0;
    }

[20170921210740666]: /images/20220608/77a7b4338db841a994c19cee203d4fe8.png