题解 | 合唱队形

#include<iostream>

using namespace std;
const int maxn = 105;
int a[maxn];
int dp[maxn];
int h[maxn];
int main() {
    int n;
    while (cin >> n) {
        for (int i = 0; i < n; i++)
            cin >> a[i];
        dp[0] = 1;
        int maxd = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (a[i] > a[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);

                }
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            h[i] = 1;
            for (int k = i; k < n; k++) {
                if (a[i] > a[k]) {
                    h[i] = max(h[i], h[k] + 1);
                }
            }
            maxd = max(maxd, dp[i] + h[i]);
        }
        cout <<n- (maxd - 1) << endl;
    }
}