查看运转结果,音乐导师要请里面包车型大巴位同学出列

1058 合唱队形

 

贰零零贰年NOIP全国际联盟赛提升组

 时间限制: 1
s

 空间范围: 12八千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

样例输出 Sample Output

4

数量范围及提示 Data Size & Hint

对于50%的数据,保证有n<=20;
对于任何的数量,保证有n<=100。

1058 合唱队形

二零零二年NOIP全国际结盟赛提升组

岁月范围: 1 s空间限制: 12八千 KB标题品级 : 黄金 Gold

题解

查看运转结果

标题陈说Description

N位同学站成一排,音乐导师要请里面包车型客车位同学出列,使得剩下的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

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

 

 

分类标签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;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;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;64         bss;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地图