经典动态规划之上升子序列问题
本题目变形了一下，需要计算两次上升子序列和下降子序列，保证子序列最长，这样出列人数就最少
附上代码 
#include<stdio.h>

int main(void)
{
    int n;
    scanf("%d",&n);
    int high[3000]={0};
    for(int i=0;i<n;i++){scanf("%d",&high[i]);}
    int dp_up[3000];
    int dp_down[3000];
    for(int i=0;i<n;i++){dp_up[i]=1;dp_down[i]=1;}
    //计算上升子序列dp_up
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(high[j]<high[i])
            {
                dp_up[i]=(dp_up[i]>dp_up[j]+1)?dp_up[i]:dp_up[j]+1;
            }
        }
    }
    //计算下降子序列dp_down
    for(int i=n-1;i>=0;i--)
    {
        for(int j=n-1;j>i;j--)
        {
            if(high[i]>high[j])
            {
                dp_down[i]=(dp_down[i]>dp_down[j]+1)?dp_down[i]:dp_down[j]+1;
            }
        }
    }
    //计算最少出列数量
    int num=0;
    for(int i=0;i<n;i++)
    {
        num=(num<dp_up[i]+dp_down[i]-1)?dp_up[i]+dp_down[i]-1:num;
    }
    printf("%d",n-num);
    return 0;
}