题解 | #合唱队#

#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
using namespace std;

int main() {
    int n;
    cin>>n;
    int dp[n+10],dp1[n+10];
    vector<int> sg(n+1);
    for(int i=0;i<=n;i++){
        dp[i]=1;
        dp1[i]=1;
    }
    sg[0]=INT_MAX;
    for(int i=1;i<=n;i++){
        cin>>sg[i];
    }
    //cout << 0x01010101 << endl;
    // for(int i=1;i<=n;i++) cout<<dp[i]<<endl;   
    for(int i=1;i<=n;i++)    //最长上升子序列
    {
        //dp[i] = 1;
        for(int j=0;j<i;j++){
            if(sg[i]>sg[j])
            dp[i]=max(dp[i], dp[j]+1);     
        }
    }
    for(int i=n;i>=1;i--){     //逆向最长上升子序列
        //dp1[i]=1;
        for(int j=i;j<=n;j++){
            if(sg[i]>sg[j])
            dp1[i]=max(dp1[i],dp1[j]+1);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++){
        res=max(res,dp[i]+dp1[i]-1);       //两个的最长相加,i被取了两次
    }
    cout<<n-res<<endl;    //需要移除的
     
}
// 64 位输出请用 printf("%lld")