学步园

合唱队形

题目描述

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

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

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

输入格式

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

输出格式

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

样例输入

8

186 186 150 200160 130 197 220

样例输出

4

题目评测链接：http://www.rqnoj.cn/Problem_26.html

同类题目扩展：http://blog.csdn.net/yuyanggo/article/details/8594315

                            http://blog.csdn.net/yuyanggo/article/details/8600067

解析：读懂题后，可以知道这道题实际上是要求以i点为最后一个点的最长上升子序列,需要删除的点个数（记为lz[i]），与以i点为起点的最长下降子序列，需要删除的点个数（记为ly[i]）。那么我们就可以枚举中点i，然后用求最长子序列长度的方法（方法链接）分别求出lz[i]与ly[i],结果就为ans=min(ans,lz[i]+ly[i]).

代码见：

动态规划+单调队列

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int T[110],lz[110],ly[110],q[110],n,len;

void init()
{
  freopen("hechang.in","r",stdin);
  freopen("hechang.out","w",stdout);
}

int find(int x)
{
  int l=1,r=len,mid;
  while(l<=r)
    {
      mid=(l+r)>>1;
      if(x>q[mid])
        l=mid+1;
      else
        r=mid-1;
    }
  return l;
}

void  work()
{
  scanf("%d",&n);
  int i;
  for(i=1;i<=n;i++)scanf("%d",&T[i]);

  q[1]=T[1]; len=1; lz[1]=0; //预处理lz[i]
  for(i=2;i<=n;i++)
    {
      if(T[i]>q[len])q[++len]=T[i];
      else if(T[i]<q[len])q[find(T[i])]=T[i];
      lz[i]=i-len;//此时的len表示以i为终点，最长上升子序列长度
    }
    
  q[1]=T[n]; len=1; ly[n]=0;//预处理ly[i]，在处理ly[i]时，从n开始逆序枚举，就可以
  for(i=n-1;i>=1;i--)         转变为与处理lz[i]的相同之问题
    {
      if(T[i]>q[len])q[++len]=T[i];
      else if(T[i]<q[len])q[find(T[i])]=T[i];
      ly[i]=n-i+1-len;
    }


  int ans=100000;
  for(i=1;i<=n;i++)ans=min(ans,lz[i]+ly[i]);
  printf("%d\n",ans);
}

int main()
{
  init();
  work();
//while(1);
  return 0;
}