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

by admin on 2018年9月19日

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。

1058 合唱队形

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

 

 

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。

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int high[110];
 5 int sdp[110];
 6 int jdp[110];
 7 int n,m,k,maxx,ans;
 8 
 9 int main()
10 {
11     cin>>n;
12     for(int i=1;i<=n;++i)
13     {
14         cin>>high[i];
15         sdp[i]=jdp[i]=1;
16     }
17     for(int i=2;i<=n;++i)
18     {
19         for(int j=i-1;j>=1;--j)
20         {
21             if(high[i]>high[j])
22             {
23                 sdp[i]=max(sdp[j]+1,sdp[i]);
24             }
25         }
26     }
27     for(int i=n-1;i>=1;--i)
28     {
29         for(int j=i+1;j<=n;++j)
30             if(high[i]>high[j])
31             {
32                 jdp[i]=max(jdp[j]+1,jdp[i]);
33             }
34     }
35     for(int i=1;i<=n;i++)
36         ans=max(ans,sdp[i]+jdp[i]);
37     cout<<n-ans+1<<endl;
38     return 0;
39 }

 

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图