题解 | #合唱队#

#include<iostream>
#include<vector>
using namespace std;
int long_seq(vector<int> s){
    int n=s.size();
    vector<int>dple(n,1);
    vector<int>dpri(n,1);
    int maxn=0;
    //找最长递增子列
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(s[j]<s[i]){
                dple[i]=max(dple[i],dple[j]+1);
            }
        }
    }
    //找最长递减子列
    for(int i=n-1;i>=0;i--){
        for(int j=n-1;j>i;j--){
            if(s[i]>s[j]){
                dpri[i]=max(dpri[i],dpri[j]+1);
            }
        }
    }
    //求和，确定以当前元素为顶点的合唱队
    for(int i=0;i<n;i++){
        maxn=max(maxn,(dple[i]+dpri[i]));
    }
    return maxn-1;//因为顶点算了两次，所以得减去一
}
int main(){
    int N;
    while(cin>>N){
        vector<int>high(N);
        for(int i=0;i<N;i++){
            cin>>high[i];
        }
        cout<<N-long_seq(high)<<endl;
    }
    return 0;
}