题解 | #合唱队#

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

int main() {
    int n;
    scanf("%d",&n);
    int hg[n];
    memset(hg, 0, sizeof(hg));

    for (int i = 0; i<n; i++) {
    scanf("%d ",&hg[i]);
    }
    int l[n],r[n];
    int dp = 0,j,k;
    memset(l, 0, sizeof(l));//保存左边满足条件的同学数(包含自己)
    memset(r, 0, sizeof(r));//保存右边满足条件的同学数

    for (int i = 0; i<n; i++) {//右侧最长下降子序列
            for (j = 0; j<i; j++) {
                if (hg[i]>hg[j]) {
                    l[i] = fmax(l[i],l[j]);
                }               
            }
            l[i] = l[i] + 1;
    }

    for (int i = n-1; i>=0; i--) {  //左侧最长上升子序列
            for (k = n-1; k>i; k--) {
                if (hg[i]>hg[k]) {
                    r[i] = fmax(r[i], r[k]);
                }
            }
            r[i] = r[i] + 1;
    }

    for (int i = 0; i<n; i++) {
        dp = fmax(dp, r[i]+l[i]-1);
    }    
        printf("%d\n", n-dp);
       // printf("%d\n", e);

    return 0;
}