题解 | #合唱队形#

#include <iostream>
using namespace std;

int flag;
int flag1;

void MaxI(int a[], int mid, int lastp, int lastn[], int len) {
    for (int i = lastp + 1; i < mid; i++) {
        if (a[i] < a[mid] && a[i] > lastn[lastn[0]]) {
            len++;
            lastn[++lastn[0]] = a[i];
            if (len > flag)
                flag = len;
            MaxI(a, mid, i, lastn, len);
            len--;
            lastn[0]--;
        }
    }
}//mid点左边最大增序列的长度
void MinI(int a[], int mid, int lastp, int lastn[], int len) {
    for (int i = lastp - 1; i > mid; i--) {
        if (a[i] < a[mid] && a[i] > lastn[lastn[0]]) {
            len++;
            lastn[++lastn[0]] = a[i];
            if (len > flag1)
                flag1 = len;
            MinI(a, mid, i, lastn, len);
            len--;
            lastn[0]--;
        }
    }
}//mid点右边最大减序列的长度
int M(int a[], int mid, int len) {
    flag = 0;
    int lastn[len];
    lastn[0] = 0;
    MaxI(a, mid, -1, lastn, 0);
    flag1 = 0;
    int lastm[len];
    lastm[0] = 0;
    MinI(a, mid, len, lastm, 0);
    return flag + flag1 + 1;
}
int main() {
    int a;
    while (cin >> a) { // 注意 while 处理多个 case
        int b[a];
        for (int i = 0; i < a; i++)
            cin >> b[i];
        int c,d=0;
        for (int i = 0; i < a; i++) {
            c= M(b, i, a);
            if(c>d)
            d=c;
        }
        cout << a-d << endl;

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