题解 | #合唱队#

看了大佬们的题解才写出来的，最长子序列··

#include<bits/stdc++.h>

using namespace std;


int main(){
    
    int n;
    while(cin>>n){
        vector<int> dp1(n,1);
        vector<int> dp2(n,1);
        vector<int> height(n,0);
        for(int i=0;i<n;++i){
            cin>>height[i];
        }
        //由左向右最长子序列
        for(int i=0;i<n;++i){
            for(int j=0;j<i;j++){
                if(height[i]>height[j])
                    dp1[i]=max(dp1[i],dp1[j]+1);
            }
        }
        //由右向左
        for(int i=n-1;i>=0;--i){
            for(int j=n-1;j>i;--j){
                if(height[i]>height[j])
                    dp2[i]=max(dp2[i],dp2[j]+1);
            }
        }
        
        int max_m=0;
        for(int i=0;i<n;++i){
            if(dp1[i]+dp2[i]-1>max_m)
                max_m = dp1[i]+dp2[i]-1;
        }
        cout<<n-max_m<<endl;
    }
    return 0;
}