1058 合唱队形 2004年NOIP全国联赛提高组

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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏python百例

84-OOP之组合

如果两个类有本质不同,其中一类的对象是另一个类对象的组件时,使用组合是最佳方案。 玩具熊还有生产厂商的信息,生产厂商的信息可以作为玩具熊的一个属性。

9530
来自专栏数据结构与算法

BZOJ2287: 【POJ Challenge】消失之物(背包dp)

第三个的转移非常神仙,反正我是没想出来,我们考虑用总的方案数减去用了改物品的方案数,我们发现直接算不是很好算,然后补集转化一下,用了物品$i$,体积为$j$,那...

9710
来自专栏程序员宝库

如何让你的代码整洁漂亮?

Robert Martin的这句话非常合适: “唯一能有效测量代码质量的方式是每分钟说多少个What-the-Fk ”** 让我深入解释一下: 做代码回顾的时...

34960
来自专栏数据结构与算法

洛谷P1622 释放囚犯

题目描述 Caima王国中有一个奇怪的监狱,这个监狱一共有P个牢房,这些牢房一字排开,第i个紧挨着第i+1个(最后一个除外)。现在正好牢房是满的。 上级下发了一...

29640
来自专栏ACM小冰成长之路

51Nod-1671-货物运输

ACM模版 描述 ? 题解 官方题解: ? 首先我们需要注意到最重要的一点,所有运输方案同时进行,我们只需要计算最后到达的方案的花费时间的最小值。所以我们需要考...

22350
来自专栏张善友的专栏

软件开发设计原则

下文摘自http://www.csdn.net/article/2015-09-06/2825621 GoF(四人帮),传说中的四位大神们,他们联手搞出了一...

24390
来自专栏JAVA高级架构

七夕情人节,程序员怎样表白更有效?

七夕情人节快乐 2017.08.28 今天是传统节日--七夕节,也是中国人传统意义上的"情人节",在此祝大家开心。然后,各大平台又被七夕节刷屏了... 作为国...

1.1K60
来自专栏架构师之路

URI设计原则,你设计的API做到了么?

咱们设计的REST API真的nice么? 优雅型:http://api.exapmle.com/louvre/da-vinci/mona-lisa 卢浮宫...

37550
来自专栏C语言及其他语言

如何到达C语言的巅峰?我推荐你阅读《C语言小白变怪兽》!

《C语言小白变怪兽》融入了作者 8 年的编程功力,以及文学级的写作能力,耗时 5 年完成,期间经过了 5 次大改版。

3.7K20
来自专栏数据结构与算法

2057. [ZLXOI2015]殉国

输入文件:BlackHawk.in   输出文件:BlackHawk.out 评测插件 时间限制:0.05 s   内存限制:256 MB 【题目描述】 ...

36080

扫码关注云+社区

领取腾讯云代金券