题解 | #合唱队#

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

int main() {
    int n;
    int a;
    cin >> n;
    vector<int> data;
    while(cin >> a)
    {
        data.push_back(a);
    }

    vector<int> dp1(n,1),dp2(n,1);
    for(int i=0;i<n;i++)//从左往右
        for(int j=0;j<i;j++)//i左边的j
            if(data[j]<data[i])
                dp1[i]=max(dp1[i],dp1[j]+1);

    for(int i=n-1;i>=0;i--)//从右往左
        for(int j=i;j<n;j++)//i右边的j
            if(data[i]>data[j])
                dp2[i]=max(dp2[i],dp2[j]+1);

    int k=0;
    for(int i=0;i<n;i++)
        k=max(k,dp1[i]+dp2[i]-1);//找队伍最长的i
    cout<<n-k<<endl;

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