题解 | #合唱队形#

#include<cstdio>
#include<iostream>
#define N 100
using namespace std;
int main() {
    int dp[N];
    int before[N];
    int A[N]{0} ;
    int after[N];
    int n ;
    scanf("%d", &n);
    for (int i = 0 ; i < n ; ++i) {
        scanf("%d", &A[i]);
    }
    for (int i = 0 ; i < n ; ++i) {
        before[i] = 0;
        after[i] = 0;
    }
    for (int i = 0 ; i < n ; ++i) {
        before[i] = 0;
        for (int j = 0 ; j < i ; ++j) {
            if (A[j] < A[i]) {
                before[i] = max(before[i], before[j] + 1);
            }
        }
    }
    for (int i = n - 1 ; i >= 0; --i) {
        after[i] = 0;
        for (int j = n - 1 ; j > i; --j) {
            if (A[j] < A[i]) {
                after[i] = max(after[i], after[j] + 1);
            }
        }
    }
    int max = 0;
    for (int i = 0 ; i < n; ++i) {
        dp[i] = after[i] + before[i] + 1;
        if (max < dp[i]) {
            max = dp[i];
        }
    }
    printf("%d\n",n-max);
}