题解 | #合唱队#

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int num,res=0,a;
    cin>>num;
    vector<int> row;
    int dp[num],dp2[num];//dp[i]表示以第i-1位同学作为结尾时的最长递增序列长度
    for(int i=0;i<num;i++){
        dp[i]=1;//初始值为1
        dp2[i]=1;
        }
    while(cin>>a)row.push_back(a);
    for(int i=1;i<num;i++)
        for(int j=0;j<i;j++)
            if(row[i]>row[j])
                dp[i]=max(dp[j]+1,dp[i]);

    for(int i=num-1;i>=0;i--)
        for(int j=num-1;j>i;j--)
            if(row[i]>row[j])
                dp2[i]=max(dp2[j]+1,dp2[i]);
    for(int i=0;i<num;i++){
        if(res<dp[i]+dp2[i]-1)
            res=dp[i]+dp2[i]-1;   
    }

    cout<<num-res<<endl;
        return 0;
    }
    
    
// 64 位输出请用 printf("%lld")