1058 合唱队形 2004年NOIP全国联赛提高组
1058 合唱队形 2004年NOIP全国联赛提高组
attack
发布于 2018-04-13 14:50:30
发布于 2018-04-13 14:50:30
1058 合唱队形
2004年NOIP全国联赛提高组
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
查看运行结果
题目描述 Description
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入描述 Input Description
输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。
输出描述 Output Description
输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
样例输入 Sample Input
8 186 186 150 200 160 130 197 220
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
对于50％的数据，保证有n<=20； 对于全部的数据，保证有n<=100。
分类标签 Tags 点此展开
遍历整个数组
求出每个值所对应的左边的上升序列和右变的下降序列
因为中间的人求了两次，所以最后-1
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 using namespace std;
6 const int MAXN=101;
7 int a[MAXN];
8 int b[MAXN];
9 int c[MAXN];
10 int f[MAXN];
11 int n;
12 void bxj(int l)
13 {
14 memset(f,0,sizeof(f));
15 for(int i=1;i<=l;i++)
16 {
17 for(int j=1;j<=i-1;j++)
18 {
19 if(a[i]>a[j])
20 {
21 f[i]=max(f[i],f[j]+1);
22 }
23 }
24 }
25 int ans=0;
26 for(int i=1;i<=l;i++)
27 {
28 if(ans<f[i]+1)
29 ans=f[i]+1;
30 }
31 b[l]=ans;
32 //b[l]=f[l];
33 }
34 void bss(int l)
35 {
36 memset(f,0,sizeof(f));
37 for(int i=l;i<=n;i++)
38 {
39 for(int j=l;j<=i;j++)
40 {
41 if(a[i]<a[j])
42 {
43 f[i]=max(f[i],f[j]+1);
44 }
45 }
46 }
47 int ans=0;
48 for(int i=l;i<=n;i++)
49 {
50 if(ans<f[i]+1)
51 ans=f[i]+1;
52 }
53 c[l]=ans;
54 }
55 int main()
56 {
57
58 scanf("%d",&n);
59 for(int i=1;i<=n;i++)
60 scanf("%d",&a[i]);
61 for(int i=1;i<=n;i++)
62 {
63 bxj(i);
64 bss(i);
65 }
66 int ans=0;
67 for(int i=1;i<=n;i++)
68 if(b[i]+c[i]>=ans)
69 ans=b[i]+c[i];
70 printf("%d",n-ans+1);
71 return 0;
72 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-04-25 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录