题解 | #合唱队#

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    int num;
    while (scanf("%d", &num) != -1) {
        int *data = (int *)malloc(sizeof(int) * num);
        for (int i = 0; i < num; i++) scanf("%d", &data[i]); /* 输入 */

        int *lis = (int *)malloc(sizeof(int) * num);
        int *lds = (int *)malloc(sizeof(int) * num);

        for (int i = 0; i < num; i++) { /* LIS */
            lis[i] = 1; for (int j = i - 1; j >= 0; j--) if (data[i] > data[j]) if (lis[i] <= lis[j]) lis[i] = lis[j] + 1;
        }

        for (int i = num - 1; i >= 0; i--) { /* LDS */
            lds[i] = 1; for (int j = i + 1; j < num; j++) if (data[i] > data[j]) if (lds[i] <= lds[j]) lds[i] = lds[j] + 1;
        }

        int max = 0;
        for (int i = 0; i < num; i++) max = ((max > (lis[i] + lds[i] - 1)) ? max : (lis[i] + lds[i] - 1)); /* max value */
        printf("%d\n", num - max);

        free(data); free(lis); free(lds);
    }
    return 0;
}