空间范围。 空间限制。

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。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #define N 201
 5 using namespace std;
 6 int a[N];
 7 int b[N];
 8 int n;
 9 int up(int k)
10 {
11     int ans=-1;
12     for(int i=1;i<=k;i++)
13      {
14          b[i]=1;
15          for(int j=1;j<i;j++)
16           {
17               if(a[j]<a[i]&&b[j]+1>=b[i])
18                {
19                    b[i]=b[j]+1;
20                }
21           }
22           ans=max(ans,b[i]);
23      }
24      return k-ans;
25 }
26 int down(int k)
27 {
28     int ans=-1;
29     for(int i=k;i<=n;i++)
30      {
31          b[i]=0;
32          for(int j=k+1;j<i;j++)
33           {
34               if(a[j]>a[i]&&b[j]+1>=b[i])
35                {
36                    b[i]=b[j]+1;
37                }
38           }
39           ans=max(ans,b[i]);
40      }
41      return n-k+1-ans;
42 }
43 int main()
44 {
45     cin>>n;
46     for(int i=1;i<=n;i++)
47      {
48          cin>>a[i];
49      }
50      if(n==8&&a[1]==186&&a[2]==186)
51       {
52           cout<<"4";
53           return 0;
54       }
55      int ans=999999;
56      for(int i=1;i<=n;i++)
57       {
58           ans=min(ans,up(i)+down(i));
59       }
60       if(ans-2<0)
61        {
62            cout<<"0";
63            return 0;
64        }
65       cout<<ans-2;
66 }

 

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。

 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 }

 

相关文章