题解 | #合唱队#

动态规划，借鉴大佬的思路。

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

int main() {
    int num=0;
    cin>>num;
    int temp;
    vector<int> mem;
    vector<int> dp1(num,0);
    vector<int> dp2(num,0);
    dp1[0]=1;
    dp2[0]=1;
    while(cin>>temp){
        mem.push_back(temp);
    }
    for(int right=0;right<num;right++){
        dp1[right]=1;
        for(int left=0;left<right;left++){
            if(mem[right]>mem[left]){
                dp1[right]=max(dp1[left]+1,dp1[right]);
            }
        }
    }
    for(int left=num-1;left+=0;left--){
        dp2[left]=1;
        for(int right=num-1;right>left;right--){
            if(mem[left]>mem[right]){
                dp2[left]=max(dp2[left],dp2[right]+1);
            }
        }
    }
    int max=0;
    for(int i=0;i<num;i++){
        max=std::max(max,dp1[i]+dp2[i]-1);
    }
    cout<<num-max;
}
// 64 位输出请用 printf("%lld")