题解 | #合唱队#

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

int main() {
    int x ;
    cin >> x;
    vector<int> v_chrom;
    v_chrom.reserve(20);
    int height;
    while (x != 0) {
        cin >> height;
        v_chrom.push_back(height);
        --x;
    }
    //l to r scan
    vector<int> dpl(v_chrom.size());
    //r to l scan
    vector<int> dpr(v_chrom.size());
    for (int i = 0; i < v_chrom.size(); ++i) {
        dpl[i] = 1;
        //比如190 201 202 200 199 198 必须扫描到最左侧，否则会少一个
        for (int j = i - 1 ; j >= 0; --j) {
            if (v_chrom[i] > v_chrom[j]) {
                dpl[i] = dpl[i] < dpl[j] + 1 ? dpl[j] + 1 : dpl[i];
            }
        }
    }
  
   //注意边界问题
    for (int i = v_chrom.size() - 1; i >= 0; --i) {
        dpr[i] = 1;
        for (int j = i + 1; j < v_chrom.size(); ++j) {
            if (v_chrom[i] > v_chrom[j]) {
                dpr[i] = max(dpr[i], dpr[j] + 1);
            }
        }
    }
    int max = 0;
    for (int i = 0 ; i < v_chrom.size(); ++i) {
        max = max > dpl[i] + dpr[i] - 1 ? max : dpl[i] + dpr[i] - 1 ;
    }

    cout <<  v_chrom.size() - max << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")