电子学会 C语言 4级 26 、 合唱队形

1264：【例9.8】合唱队形

信息学奥赛一本通（C++版）在线评测系统

2711:合唱队形

OpenJudge - 2711:合唱队形

 【问题描述】

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，

使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：

设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK，

则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1≤i≤K)。

你的任务是，已知所有N位同学的身高，

计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

【输入文件】

输入文件chorus.in的第一行是一个整数N（2 ≤ N ≤ 100），

表示同学的总数。第二行有n个整数，用空格分隔，

第i个整数Ti（130 ≤ Ti ≤ 230）是第i位同学的身高（厘米）。

【输出文件】

输出文件chorus.out包括一行，

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

【样例输入】

8

186 186 150 200 160 130 197 220

【样例输出】

4

【例8】合唱队形（《信息学奥赛一本通第五版》）

https://www.cnblogs.com/Benjamin-cpp/p/10816367.html

https://www.cnblogs.com/EdSheeran/p/7629975.html

合唱队形（简单的动规）_合唱队列的编法_wspl654321的博客-CSDN博客

合唱队形（信息学奥赛一本通-T1264）_合唱队形 一本通_Alex_McAvoy的博客-CSDN博客

合唱队形【DP】_ssl_fuyang的博客-CSDN博客

【DP】合唱队形_SSL_Maple的博客-CSDN博客

【动态规划】合唱队形_)NCuyALnA$Ke的博客-CSDN博客

https://blog.csdn.net/sdauguanweihong/article/details/86247847

合唱队形----dp_合唱队行问题_scwMason的博客-CSDN博客

luogu1091：合唱队形_liusu201601的博客-CSDN博客

C++参考代码：

#include<cstring>
#include<iostream>
using namespace std;
int a[200],b[200],c[200];
main()
{
  	int n,i,j,maxx;
  	
  	//读学生数
	cin>>n;                                         
  	
  	//身高满足递增顺序的两个队列初始化
	memset(b,0,sizeof(b));   
  	memset(c,0,sizeof(c)); 
  
  	//读每个学生的身高
  	for (i=1;i<=n;i++)                          
   		cin>>a[i];
  
  	//按照由左而右的顺序计算b序列
  	//最长的上升序列 
	for (i=1;i<=n;i++)            
	{
		b[i]=1;
		for (j=1;j<=i-1;j++)
	  		if ( (a[i]>a[j]) && (b[j]+1>b[i]) )
	   			b[i]=b[j]+1;
	}   

	//按照由右而左的顺序计算c序列
	for (i=n;i>=1;i--)                   
	{
	    c[i]=1;
	    for (j=i+1;j<=n;j++)
	      if ((a[i]>a[j])&&(c[j]+1>c[i]))
	        c[i]=c[j]+1;
	} 
  
    //计算合唱队的人数max（其中1人被重复计算） 
	maxx=0;                   
    for (i=1;i<=n;i++)
       	if ( b[i]+c[i] > maxx )
          maxx=b[i]+c[i];
  	
	//输出出列人数
	cout<<n-(maxx-1)<<endl;
	
	return 0;                
}
/*
这个算法的时间复杂度为O(n^2)，
在1秒时限内可解决n≤100范围内的问题。
*/

电子学会青少年编程等级考试

https://blog.csdn.net/dllglvzhenfeng/category_11735875.html

中国电子学会考评中心

中国电子学会考评中心

软件编程（C语言）

中国电子学会考评中心