题解 | #合唱队#

#include <bits/stdc++.h>
#include <vector>
using namespace std;
int N;
int max_people=0;
vector<int> long_(vector<int>h)
{
        vector<int> dp(N,1);
        for(int i=1;i<N;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(h[j]<h[i]) dp[i]=max(dp[i],dp[j]+1);
            }
        }
        return dp;
}
int main() {
    while(cin>>N)
    {
        vector<int> h(N,0);
        for(int i=0;i<N;i++)
            cin>>h[i];//处理输入
        vector<int> res1=long_(h);////从前往后求解以i结尾的最长上升序列长度
        reverse(h.begin(),h.end());//逆置一下
        vector<int> res2=long_(h);
        for(int i=0;i<h.size();i++)
            max_people=max(res1[i]+res2[N-i-1],max_people);//逆置以后编号改变了,i对应N-i-1
        cout<<N-max_people+1<<endl;
    } 
}