1264:【例9.8】合唱队形 2021-01-15

简介: 1264:【例9.8】合唱队形 2021-01-15

1264:【例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

【输出样例】

4

【提示】

对于50%的数据,保证有n≤20;

对于全部的数据,保证有n≤100。

1. #include <iostream>
2. #include <cstdio>
3. using namespace std;
4. int a[200],b[200],c[200];
5. int main(int argc, char *argv[])
6. {
7.  int n,i,j,maxx;
8.  cin>>n;
9.  for(i=1;i<=n;i++) cin>>a[i];
10.   //b[i]从左到右满足身高递增的人数 
11.   for(i=1;i<=n;i++){
12.     b[i]=1;
13.     for(j=1;j<=i-1;j++)
14.       if((a[i]>a[j])&&(b[j]+1>b[i]))
15.         b[i]=b[j]+1;
16.   }
17. 
18. //  for(i=1;i<=n;i++)cout<<b[i]<<" ";
19. //  cout<<endl;
20. 
21.   //c[i]从右到左满足身高递增的人数
22.   for(i=n;i>=1;i--){
23.     c[i]=1;
24.     for(j=i+1;j<=n;j++)
25.       if((a[j]<a[i])&&(c[j]+1>c[i]))
26.         c[i]=c[j]+1;
27.   }
28. 
29. //  cout<<endl;
30. //  for(i=1;i<=n;i++)cout<<c[i]<<" ";
31. //  cout<<endl;
32. 
33.   //统计同时满足最优的最大数量 
34.   maxx=0;
35.   for(i=1;i<=n;i++)
36.     if(b[i]+c[i]>maxx)
37.       maxx=b[i]+c[i];
38.   //减去被重复使用的i同学 
39.   cout<<n-maxx+1<<endl;
40.   return 0;
41. }


目录
打赏
0
0
0
0
3
分享
相关文章
OpenCV中线段、矩形、圆形、多边形的讲解与绘制实战(附Python源码)
OpenCV中线段、矩形、圆形、多边形的讲解与绘制实战(附Python源码)
221 0
|
10月前
cavans图形绘制(直线、矩形、原型、贝塞尔曲线、渐变背景) 2
cavans图形绘制(直线、矩形、原型、贝塞尔曲线、渐变背景) 2
canvas系列教程01——直线、三角形、多边形、矩形、调色板
canvas系列教程01——直线、三角形、多边形、矩形、调色板
252 0
|
10月前
cavans图形绘制(直线、矩形、原型、贝塞尔曲线、渐变背景) 1
cavans图形绘制(直线、矩形、原型、贝塞尔曲线、渐变背景)
140.递归法绘制三角形图案
140.递归法绘制三角形图案
107 0
【OpenGL】十三、OpenGL 绘制三角形 ( 绘制单个三角形 | 三角形绘制顺序 | 绘制多个三角形 )(二)
【OpenGL】十三、OpenGL 绘制三角形 ( 绘制单个三角形 | 三角形绘制顺序 | 绘制多个三角形 )(二)
158 0
【OpenGL】十三、OpenGL 绘制三角形 ( 绘制单个三角形 | 三角形绘制顺序 | 绘制多个三角形 )(二)
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等