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

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 }

 

相关文章

Leave a Comment.