题解 | #合唱队#

#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> T;
    for(int i = 0;i<N;++i){
        int Ttemp;
        cin >> Ttemp;
        T.emplace_back(Ttemp);
    }
    //动态规划求最长递增子串
    vector<int> dpincrease(N,1);
    for(int i = 1;i<N;++i){
        for(int j = i-1;j>=0;--j){
            if(T[i] > T[j])dpincrease[i] = max(dpincrease[i],dpincrease[j]+1);
        }
    }
    //动态规划求最长递减子串
    vector<int> dpdecrease(N,1);
    for(int i = N-1;i>=0;--i){
        for(int j = i+1;j<N;++j){
            if(T[i] > T[j])dpdecrease[i] = max(dpdecrease[i],dpdecrease[j]+1);
        }
    }
    int res = 0;//最少踢出人数
    for(int i = 0;i<N;++i){
        if(dpincrease[i] != 1 && dpdecrease[i]!=1)res = max(res,dpincrease[i]+dpdecrease[i]);
    }
    
    cout << N-res+1 << endl;
    return 0;
}