题解 | #合唱队#

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

int main() {
    int len;
    cin>>len;
    int count =len;
    vector<int> talls;
    while(count--)
    {
        int a;
        cin>>a;
        talls.push_back(a);
    }
    //计算左侧最大子串
    vector<int> numL(len,1);
    for(int i = 0; i < len; i++)
    {
        for(int t = 0; t <= i; t++)
        {
            if(talls[i]>talls[t])
            {
                numL[i] = max((numL[t]+1),numL[i]); 
            }

        }
    }
    //计算右侧最大子串
    vector<int>numR(len,1);
    for(int i = len -1; i >=0;i--)
    {
        for(int t = len -1; t>=i;t--)
        {
            if(talls[i]>talls[t])
            {
                numR[i] = max(numR[t]+1,numR[i]); 
            }
        }
    }

    vector<int> num(len,0);
    int maxNum = 0;
    for(int i = 0; i<len;i++)
    {
        num[i] = numL[i]+numR[i]-1;
        if(num[i]>maxNum)
            maxNum = num[i];
    }
    cout<<len-maxNum;

    
    
    

    
    
}
// 64 位输出请用 printf("%lld")