合唱队形大合唱队形创意图-爱华网

合唱队形

Description

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …,TK，则他们的身高满足T1 < T2 < …< Ti , Ti > Ti+1 > …> TK (1 <= i <=K)。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

Input

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

Output

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

Sample Input

186 186 150 200 160 130 197 220

Sample Output

解题思路：这题在今天又做了一边，并且思路更清晰了，其实大意是求出去掉最少的人数后，剩下的人构成一个先递增后递减的队形，顺序要求不能改变。想到了动规求最长递增子序列，如果我们用两个数组分别存放以每个对应元素为结尾的最长递增子序列和最长递减最长递减子序列，那么对应位置的两个数组元素之和就是留下来的人数和（还要减一，因为分界的元素被加了两次），那么去掉的人数就是最少的了。

代码如下：

#include<iostream>
using namespace std;
int Queue[110],Inc[110],Dec[110];
int main()
{
      int N;
    scanf("%d",&N);
   for(int i=0;i<N;i++)
             scanf("%d",&Queue[i]);
    memset(Inc,0,sizeof(Inc));
        memset(Dec,0,sizeof(Dec));
        for(int i=0;i<N;i++)
       {
               Inc[i]=1;
               for(int j=0;j<i;j++)
             {
                     if(Queue[i]>Queue[j]&&Inc[j]+1>Inc[i])
                        Inc[i]=Inc[j]+1;
                }
 }
 for(int i=N-1;i>=0;i--)
    {
               Dec[i]=1;
               for(int j=N-1;j>i;j--)
           {
                     if(Queue[i]>Queue[j]&&Dec[j]+1>Dec[i])
                        Dec[i]=Dec[j]+1;
                }
 }
 int max=0;
        for(int i=0;i<N;i++)
       {
               if(Inc[i]+Dec[i]>max)

                  max=Inc[i]+Dec[i];
        }
 printf("%dn",N-max+1);
   return 0;
}