空中限制, 空间限制

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

1058 合唱队形

2004年NOIP全国际缔盟赛提升组

时限: 一 s

空间范围: 12九千 KB

标题等级 : 黄金 戈尔德

 

 

 

难题叙述 Description

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

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

    你的职分是,已知全体N位同学的身高,总结最少须求四个人同学出列,能够使得剩下的同班排成合唱队形。

输入描述 Input Description

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

输出描述 Output Description

 
  输出文件chorus.out包含一行,那一行只含有2个整数,就是至少需求3位同学出列。

样例输入 萨姆ple Input

8
186 186 150 200 160 130 197 220

样例输出 Sample Output

4

数量范围及提醒 Data Size & Hint

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

 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 }

 

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

    你的职分是,已知全部N位同学的身高,计算最少须求几位同学出列,能够使得剩下的同学排成合唱队形。

8
186 186 150 200 160 130 197 220

 时限: 一s

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

 标题等级 : 黄金
戈尔德

输入描述 Input Description

200四年NOIP全国际联盟赛进步组

题材叙述 Description

样例输入 萨姆ple Input

十5捌 合唱队形

 
  输出文件chorus.out包蕴一行,那壹行只包蕴1个平头,正是最少要求几个人同学出列。

 

数量范围及提示 Data Size & Hint

样例输出 萨姆ple Output

4

 空间限制: 128000KB

出口描述 Output Description

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

 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地图