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
分享
相关文章
|
5月前
|
Z字形变换
本题要求实现一个函数 `convert`,将给定字符串按指定行数以Z字形排列,再按行读取生成新字符串。示例中,字符串 &quot;LEETCODEISHIRING&quot; 在3行和4行下的变换结果分别为 &quot;LCIRETOESIIGEDHN&quot; 和 &quot;LDREOEIIECIHNTSG&quot;。Java代码通过列表存储每行字符,控制方向变化完成Z字形排列,最后合并各行得到结果。
29 1
|
10月前
cavans图形绘制(直线、矩形、原型、贝塞尔曲线、渐变背景) 2
cavans图形绘制(直线、矩形、原型、贝塞尔曲线、渐变背景) 2
|
10月前
cavans图形绘制(直线、矩形、原型、贝塞尔曲线、渐变背景) 1
cavans图形绘制(直线、矩形、原型、贝塞尔曲线、渐变背景)
|
11月前
|
C++
字形变换(C++)
字形变换(C++)
51 0
关于已知线段,如何求封闭图形轮廓的一些猜想
关于已知线段,如何求封闭图形轮廓的一些猜想
【c++】C语言之输入行数,输出实心菱形和空心菱形
C语言之输入行数,输出实心菱形和空心菱形
1425 1
【c++】C语言之输入行数,输出实心菱形和空心菱形
AI助理

你好,我是AI助理

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