题解 | #合唱队形#

解题思路：

• 队形的特征是从,对于最小剔除多少个人，只要左往右寻找最长严格上升子序列，以及从右往左寻找最长严格上升子序列
• 遍历整个队列，寻找$l->i->rl\; ->\; i\; ->\; r$的每一个以i为终点的左侧最长上升子序列和右侧最长上升子序列 - 1，就是最大的长度$lnln$。那么剔除的人数只要$n-lnn\; -\; ln$就是答案。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> stu(n);
    for(int i = 0; i < n; ++i){
        cin>>stu[i];
    }
    vector<int> dpl(n);
    for(int i = 0; i < n; ++i){//左侧最长严格上升子序列
        int mx = 0;
        for(int j = 0; j < i; ++j){
            if(stu[i] > stu[j]) mx = max(mx, dpl[j]);
        }
        dpl[i] = mx+1;
    }
    vector<int> dpr(n);
    for(int i = n-1; i >= 0; --i){//右侧最长严格上升子序列
        int mx = 0;
        for(int j = n-1; j > i; --j){
            if(stu[i] > stu[j]) mx = max(mx,dpr[j]);
        }
        dpr[i] = mx+1;
    }
    int ans = 0;
    for(int i = 0; i < n; ++i){//求得最长的队形
        ans = max(dpl[i] + dpr[i]-1, ans);
    }
    cout<<n-ans<<endl;
    return 0;
}