澳门真人网上娱乐网址题目叙述Description, 查看运营结果

105八 合唱队形

 

200肆年NOIP全国际联盟赛升高组

 时限: 1s

 空间范围: 128000KB

 标题等级 : 黄金
戈尔德

题解

 查看运转结果

 

 

主题素材叙述 Description

   
N位同学站成壹排,音乐老师要请里面包车型大巴(N-K)位同学出列,使得剩下的K位同学排成合唱队形。

    合唱队形是指那样的壹种队形:设K位同学从左到右依次编号为一,二…,K,他们的身高分别为T一,T二,…,TK,  则他们的身高知足T1<…<Ti>Ti+一>…>TK(一<=i<=K)。

    你的天职是,已知全体N位同学的身高,总计最少必要三人同学出列,能够使得剩下的同桌排成合唱队形。

输入描述 Input Description

 
  输入文件chorus.in的率先行是一个整数N(二<=N<=100),表示同学的总和。第二行有n个整数,用空格分隔,第i个整数Ti(130<=Ti<=230)是第i位同学的身高(分米)。

输出描述 Output Description

 
  输出文件chorus.out包罗1行,那壹行只含有二个整数,便是起码要求2个人同学出列。

样例输入 Sample Input

8
186 186 150 200 160 130 197 220

样例输出 萨姆ple Output

4

数量范围及提醒 Data Size & Hint

对于50%的数据,保证有n<=20;
对于整个的数码,保障有n<=100。

拾58 合唱队形

2004年NOIP全国际联盟赛进步组

岁月范围: 一 s空间限制: 128000 KB标题等第 : 黄金 高尔德

题解

查阅运转结果

标题叙述Description

N位同学站成一排,音乐老师要请里面包车型地铁位同学出列,使得剩下的K位同学排成合唱队形。

合唱队形是指那样的1种队形:设K位同学从左到右依次编号为一,二…,K,他们的身高分别为T一,T②,…,TK,则他们的身高满意T1<…<Ti>Ti+壹>…>TK(壹<=i<=K)。

您的职分是,已知全数N位同学的身高,总括最少须要三位同学出列,可以使得剩下的同校排成合唱队形。

输入描述Input Description

输入文件chorus.in的首先行是3个整数N(二<=N<=拾0),表示同学的总额。第2行有n个整数,用空格分隔,第i个整数Ti(130<=Ti<=230)是第i位同学的身高。

输出描述Output Description

输出文件chorus.out包含一行,那一行只含有3个平头,就是最少必要几位同学出列。

样例输入山姆ple Input

8
186 186 150 200 160 130 197 220

样例输出萨姆ple Output

4

数量范围及提示Data Size & Hint

对于50%的数据,保证有n<=20;
对于整个的数码,保障有n<=十0。

分拣标签 Tags 点此开始展览 

 遍历整个数组

求出每种值所对应的右侧的上涨类别和右变的降低系列

因为中间的人求了三次,所以最终-壹

 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 #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 }