题解 | #合唱队#

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


int main(){

    int n;
    scanf("%d", &n);

    int tall[n];
    memset(tall, 0, sizeof(tall));
    for(int i = 0; i < n; i++){
        scanf("%d", tall + i);
    }

    int inc[n], dec[n], sum[n];
    memset(inc, 0, sizeof(inc));
    memset(dec, 0, sizeof(dec));
    memset(sum, 0, sizeof(sum));

    for(int i = n - 1; i >= 0; i--){
        for(int j = i + 1; j < n; j++)
        {
            if(tall[i] > tall[j] && dec[i] < dec[j] + 1)
                dec[i] = dec[j] + 1;
            }

    }

    for(int i = 0; i < n; i++){
        for(int j = i - 1; j >= 0; j--){
            if(tall[i] > tall[j] && inc[i] < inc[j] + 1){
                inc[i] = inc[j] + 1;
            }
        }

    }


    int max = 0;
    for(int i = 0; i < n; i++){
        sum[i] = inc[i] + dec[i];
        max = max > sum[i] ? max : sum[i];
    }

    printf("%d", n - max - 1);

    return 0;
}