题解 | #合唱队#

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        int t;
        vector<int> v;
        for(int i=0;i<n;i++)
        {
            cin>>t;
            v.push_back(t);
        }
        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(v[j]<v[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(v[i]>v[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;
    }
}