题解 | 合唱队

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
const int N = 1e7 + 5;
void solve(){
    int n;
    cin >> n;
    vector<int>v(n + 1);
    for(int i = 1 ; i <= n ; i++){
        cin >> v[i];
    }
    int ans = -1;
    for(int k = 1 ; k <= n ; k++){
        vector<int>s,x;
        s.push_back(v[1]),x.push_back(v[k]);
        for(int i = 2 ; i <= k ; i++){
            if(v[i] > s.back()){
                s.push_back(v[i]);
            }
            else{
                *lower_bound(s.begin(),s.end(),v[i]) = v[i];
            }
        }
        for(int j = k + 1 ; j <= n ; j++){
            if(v[j] < x.back()){
                x.push_back(v[j]);
            }
            else{
                *lower_bound(x.begin(),x.end(),v[j],greater<int>()) = v[j];
            }
        }
        ans = max(ans,(int)(s.size() + x.size()) - 1);
    }
    cout << n - ans;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
}

稍微有点小难，但是很经典，大部分人应该见过了，我们枚举每个点作为中间的点，然后求前后的最长上升子序列和最长下降子序列，然后取和的max，显而易见这种方法可以包含所有的情况，最后输出n - ans就是要踢出去的人数