NOIP2004提高组题3 合唱队形

admin

三、合唱队形

(chorus.pas／dpr／c／cpp)

【问题描述】

    N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

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

    你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

【输入文件】

    输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

【输出文件】

    输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

【样例输入】

8
186 186 150 200 160 130 197 220

【样例输出】

4

【数据规模】

对于50％的数据，保证有n<=20；
对于全部的数据，保证有n<=100。

Settwarl

效率不太高的方法：

1. #include<iostream>
   
2. #include<cstdio>
   
3. using namespace std;
   
4. int n,t[101],a[101]={0},k=0,kf=0;
   
5. bool down(int);
   
6. int next(int i)
   
7. {
   
8.     int ii=i;
   
9.     do
   
10.     {
    
11.         i++;
    
12.         if(i>n)return ii;
    
13.     }while(a[i]==0);
    
14.     return i;
    
15. }
    
16. void save()
    
17. {
    
18.     kf=kf<k?k:kf;
    
19. }
    
20. void mysearch(int p)
    
21. {
    
22.     if((p>n)&&(down(p)))
    
23.     {
    
24.         save();
    
25.     }
    
26.     else for(int i=p;i<=n;i++)
    
27.     {
    
28.         if(a[i]==0)
    
29.         {
    
30.             k++;
    
31.             a[i]=1;
    
32.             if(down(i))
    
33.                 mysearch(p+1);
    
34.             a[i]=0;
    
35.             k--;
    
36.             if(down(i))
    
37.                 mysearch(p+1);
    
38.         }
    
39.     }
    
40. }
    
41. int main()
    
42. {
    
43. 
    
44.     cin>>n;
    
45.     for(int i=1;i<=n;i++)
    
46.         cin>>t[i];
    
47.     mysearch(1);
    
48.     cout<<n-kf;
    
49.     return 0;
    
50. }
    
51. bool down(int p)
    
52. {
    
53.     bool b=true;
    
54.     int mx=1,i;
    
55.     while((mx<p)&&(t[mx]<t[next(mx)]))mx++;
    
56.     for(i=mx;i<p;i++)
    
57.         if((a[i]==1)&&(t[i]<=t[next(i)])&&(i!=next(i)))b=false;
    
58.     return b;
    
59. }
    

复制代码

hr567

Settwarl 发表于 2014-10-28 20:18
效率不太高的方法：

膜拜大神，我完全不知道怎么写

/wjr/

这是我的做法：n个最长上升子序列和最长下降子序列。。。并上并行读取。。。

1. #include<iostream>
   
2. using namespace std;
   
3. int n,a[10010],ans1[10010],ans2[10010],ans[10010],k=9999999;
   
4. int main()
   
5. {
   
6.         cin>>n;
   
7.         for(int i=1;i<=n;i++)
   
8.         {
   
9.                 cin>>a[i];
   
10.                 for(int j=1;j<=i;j++)
    
11.                 if(a[i]>a[j])ans1[i]=max(ans1[i],ans1[j]+1);
    
12.         }
    
13.         for(int i=n;i>=1;i--)
    
14.         for(int j=n;j>=i;j--)
    
15.         if(a[i]>a[j])ans2[i]=max(ans2[i],ans2[j]+1);
    
16.         for(int i=1;i<=n;i++)
    
17.         {
    
18.                 ans[i]=ans1[i]+ans2[i];
    
19.                 k=min(k,n-ans[i]);
    
20.         }
    
21.         if(k!=9999999)cout<<k-1;
    
22.         return 0;
    
23. }

复制代码

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. int n,a[110],f1[110],max1,f2[110],max2,ans;
   
4. int i,j,k;
   
5. int main()
   
6. {
   
7.     cin>>n;
   
8.     for(i=1;i<=n;i++)cin>>a[i];
   
9.     for(i=1;i<=n;i++)
   
10.     {
    
11.         f1[i]=1;
    
12.         f2[i]=1;
    
13.     }
    
14.     for(i=2;i<=n;i++)
    
15.         for(j=1;j<=i-1;j++)
    
16.             if(a[i]>a[j]) f1[i]=max(f1[i],f1[j]+1);
    
17.     for(i=n-1;i>=1;i--)
    
18.         for(j=n;j>=i+1;j--)
    
19.             if(a[i]>a[j]) f2[i]=max(f2[i],f2[j]+1);
    
20.     for(i=1;i<=n;i++)
    
21.       ans=max(ans,f1[i]+f2[i]-1);
    
22.     ///cout<<ans<<endl;
    
23.     cout<<(n-ans);
    
24. }
    

复制代码