C++题解 | #合唱队#

直接从前求一遍最长递增子序列，从后再求一遍，然后对应累加-1求最大值max即可，最后输出N-max

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

int main (){
    int N, max = 1;
    cin >> N;
    vector<int> num(N), dpf(N,1), dpb(N, 1);
    for(int i = 0; i < N; ++i)
        cin >> num[i];
    for(int i = 1; i < N; ++i)
        for(int j = 0; j < i; ++j)
            if(num[i] > num[j] && dpf[i] < dpf[j] + 1)
                dpf[i] = dpf[j] + 1;
    for(int i = N-2; i >= 0; --i)
        for(int j = N-1; j > i; --j)
            if(num[i] > num[j] && dpb[i] < dpb[j] + 1)
                dpb[i] = dpb[j] + 1;
    for(int i = 1; i < N; ++i)
        if(max < dpf[i] + dpb[i] - 1)
            max = dpf[i] + dpb[i] - 1;
    cout << N - max;
}