题解 | #合唱队形#

#include <iostream>
using namespace std;

int arr[200]; //初始数组
int dpl[200]; //从左边往右边的dp
int dpr[200]; //从右边往左边的dp

int main() {
    int N;
    while (scanf("%d", &N) != EOF) {
        fill(dpl, dpl + N, 1); //初始化为1
        fill(dpr, dpr + N, 1); //初始化为1
	  
        for (int i = 0; i < N; i++) { //初始化数组
            scanf("%d", &arr[i]);
        }
	  
        //中间数 的 左边是最长递增序列， 右边是最长递减序列
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dpl[i] = max(dpl[i], dpl[j] + 1);
                }
            }
        }
        for (int i = N - 2; i >= 0; i--) {
            for (int j = N - 1; j > i; j--) {
                if (arr[i] > arr[j]) {
                    dpr[i] = max(dpr[i], dpr[j] + 1);
                }
            }
        }
        
        int maxlen = 0;
        for (int i = 0; i < N; i++) {
            int t = dpr[i] + dpl[i] - 1; //为什么要减1，因为中间这个值算了两次
            maxlen = max(maxlen, t);
        }
        printf("%d\n", N - maxlen);
    }

}
// 64 位输出请用 printf("%lld")