华师一附中OI组

标题: NOIP2004提高组题3 合唱队形 [打印本页]
作者: admin    时间: 2014-10-21 16:46
标题: NOIP2004提高组题3 合唱队形
三、合唱队形

(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    时间: 2014-10-28 20:18
效率不太高的方法：
  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. {

  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    时间: 2014-10-28 21:47
Settwarl 发表于 2014-10-28 20:18
效率不太高的方法：

膜拜大神，我完全不知道怎么写
作者: /wjr/    时间: 2014-11-4 21:42
这是我的做法：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. }
复制代码
作者: 倚窗倾听风吹雨    时间: 2018-9-30 18:56
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2