题解 | #合唱队#

解题思路: 这道题关键点在于求每个人左右两边最大留住的人数。拿每个人左边为例，每个人左边的人身高必须比这个人要小，按这个逻辑这个人左边的每一个人都有其最大的留住人数max,然后求左边每个人的max里的最大值加1，加1是因为要把左边符合逻辑的人包含在内。 右边的逻辑同理。 动态规划我的理解就是把复杂的问题分解成逻辑相同的原子问题，然后原子问题堆积成原有问题。难点在于对复杂问题的分析，怎样抽象出原子问题是动态规划的难点。

#include<vector>
using namespace std;
int main(){
    vector<int> num;
    int n=0,number=0;
    int i=0,j=0,min=0;
    int * left;
    int * right;
    while(cin>>n){
        min=n+1;
        left=new int[n]{0};
        right=new int[n]{0}; 
        for(i=0;i<n;i++){
            cin>>number;
            num.push_back(number);
        }
        /*计算左边最大的人数*/
        for(i=0;i<n;i++){
            for(j=0;j<i;j++){
                if(num[j]<num[i]){
                    if(left[j]>=left[i]){
                        left[i]=left[j]+1;
                    }
                }
            }

        }
        /*计算右边最大的人数*/
        for(i=n-1;i>=0;i--){
            for(j=n-1;j>i;j--){
                if(num[j]<num[i]){
                    if(right[j]>=right[i]){
                        right[i]=right[j]+1;
                    }
                }
            }  
        }
        /*计算出列最少的人数*/
        for(i=0;i<n;i++){
            j=n-left[i]-right[i]-1;
            if( j<min)
                min=j;
        }
        cout<<min<<endl;
        delete []left;
        delete []right;
        num.clear();
    }
    return 0;
}