题解 | 合唱队形

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 101;
int n;
int a[N], b[N], c[N];

//思路：利用状态表示数组b[], c[]分别求出以i结尾的最长上升子序列 和 以i开头的最长下降子序列

int res() {
    if (n == 0) return 0;//处理边界
    for (int i = 0; i < n; i++) {
        b[i] = 1;
        c[i] = 1;//均初始化为1，即最短时为自身
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i])
                b[i] = max(b[i], b[j] + 1);
        }
    }//此时b[]记录完毕
    for (int i = n - 1; i >= 0; i--) {//要反向遍历否则会导致依赖的后续状态未被正确计算
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[i])
                c[i] = max(c[i], c[j] + 1);
        }
    }//c[]记录完毕
    int result = 99;
    for (int i = 0; i < n; i++) result = min(result, n - b[i] - c[i] + 1);
    return result;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << res() << endl;
    return 0;
}