空间范围, 查看运行结果

1058 合唱队形

 

二零零四年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包蕴一行,这一行只含有一个平头,就是起码要求几位同学出列。

样例输入 萨姆ple Input

8
186 186 150 200 160 130 197 220

样例输出 山姆ple Output

4

数码范围及提示 Data Size & Hint

对于50%的数据,保证有n<=20;
对此任何的多少,有限支撑有n<=100。

1058 合唱队形

 

二零零四年NOIP全国联赛提高组

 时间限制: 1
s

 空间范围: 128000
KB

 标题等级 : 黄金
高尔德

题解

 查看运行结果

 

 

题材叙述 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

样例输出 山姆ple 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 }

 

 

分拣标签 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 }

 

 

相关文章

网站地图xml地图