空中限制, 空间限制

1058 合唱队形

1058 合唱队形

2000年NOIP全国际订盟赛提升组

时间限制: 1 s

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

 

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

 时限: 1
s

 空间限制: 12玖仟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富含一行,这一行只蕴含三个整数,正是起码必要四个人同学出列。

样例输入 萨姆ple Input

8
186 186 150 200 160 130 197 220

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