题目描述

计算最少出列多少位同学，使得剩下的同学排成合唱队形

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

注意不允许改变队列元素的先后顺序
请注意处理多组输入输出！

输入

8
186 186 150 200 160 130 197 200

输出

4

需要出列的同学最少 = 保留下来的同学最多。
最后排成的合唱队是△先递增再递减的，中间会有一个最高的中心同学i。
当中心同学i左边的同学+右边同学最多的时候，保留下的同学最多。
即i左边的最长递增子序列 + i右边的最长递减子序列最大的时候是最优解。
先求i处最长递增子序列的个数：dp_up[i]=max(dp_up[i],dp_up[j]+1); 其中j<i;从左往右循环。
再求i处最长递减子序列的个数：dp_down[i]=max(dp_down[i],dp_down[j]+1);其中j>i;从右往左循环。
当i处dp_up[i]+dp_down[i]最大时，i就是中心同学，此时队列中人数dp_up[i]+dp_down[i]-1
出列的人数：总人数num-(dp_up[i]+dp_down[i]-1)

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int num;
    while(cin>>num){
        vector<int> temp;
        vector<int> dp_up(num,1);
        vector<int> dp_down(num,1);
        for(int i=0;i<num;i++){
            int a;
            cin>>a;
            temp.push_back(a);
        }
        //dp_up[i]最长上升子序列个数
        for(int i=1;i<temp.size();i++){
            for(int j=i-1;j>=0;j--){
                if(temp[j]<temp[i]){
                    dp_up[i]=max(dp_up[i],dp_up[j]+1);
                }
            }
        }
        //dp_down[i]最长下降子序列个数
        for(int i=temp.size()-2;i>=0;i--){
            for(int j=i+1;j<temp.size();j++){
                if(temp[j]<temp[i]){
                    dp_down[i]=max(dp_down[i],dp_down[j]+1);
                }
            }
        }
        int maxvalue=0;
        for(int i=0;i<temp.size();i++){
            if(dp_up[i]+dp_down[i]>maxvalue)
                maxvalue=dp_up[i]+dp_down[i];
        }
        cout<<num-(maxvalue-1)<<endl;

    }
}