题解 | #合唱队形#

#include "stdio.h"
#include "climits"
using namespace std;

int n;//学生人数
int student[110];// 存储学生身高
int leftDP[110];//存储从左到右的最长上升子序列长度
int rightDP[110];//存储从右到左的最长上升子序列长度

void LISDP(){
    leftDP[0] = 1;int max = 0;
    for (int i = 1; i < n; ++i) {//求leftDP
        max = 1;
        for (int j = 0; j < i; ++j) {
            if(student[j] < student[i]){
                if(leftDP[j] + 1 > max)
                    max = leftDP[j] + 1;
            }
        }
        leftDP[i] = max;
    }
    rightDP[n-1] = 1;
    for (int i = n-2; i >= 0; --i) {
        max = 1;
        for (int j = n-1; j > i; --j) {
            if(student[j] < student[i]){
                if(rightDP[j] + 1 > max)
                    max = rightDP[j] + 1;
            }
        }
        rightDP[i] = max;
    }
}

int main(){

    while (scanf("%d",&n)!=EOF){
        if(n == 2){
            printf("0\n");
            continue;
        }
        for (int i = 0; i < n; ++i) {
            scanf("%d",student+i);
        }
        LISDP();
        int max = INT_MIN;
        for (int i = 0; i < n; ++i) {
            if(i == 0){
                max = max<rightDP[0]?rightDP[0]:max;
            }
            if(i == n-1){
                max = max<leftDP[n-1]?leftDP[n-1]:max;
            }
            int temp = leftDP[i] +rightDP[i];
            if(max < temp-1)//减1是因为下标为i的同学算了两遍
                max = temp-1;
        }

        printf("%d\n",n-max);
    }
}