题解 | #合唱队形#

详细视频讲解看这个视频： https://www.bilibili.com/video/BV1t64y1u7Cu

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1001;

int a[MAXN];
int dp1[MAXN];
int dp2[MAXN];

int n;
int MAXL;

int main(){
    cin >> n;
    //输入一排同学的身高
    for(int i = 1; i <= n; i++){    
        cin >> a[i];
    }
    //dp1[i]表示以i为终点的最长上升序列的高度
    dp1[1] = 1;
    for(int i = 2; i <= n; i++){
        MAXL = 0;
        for(int j = 1; j <= i-1; j++){
            if(a[i] > a[j]){
                if(dp1[j] > MAXL){
                    MAXL = dp1[j];
                }
            }
        }
        dp1[i] = MAXL + 1;
    }
    //dp2[i]表示以i为起点的最长下降序列的高度
    dp2[n] = 1;
    for(int i = n - 1; i >= 1; i--){
        MAXL = 0;
        for(int j = i+1; j <= n; j++){
            if(a[i] > a[j]){
                if(dp2[j] > MAXL){
                    MAXL = dp2[j];
                }
            }
        }
        dp2[i] = MAXL + 1;
    }
    int res = 0;
    for(int i = 1; i <= n; i++){
        if(dp1[i] + dp2[i] > res){
            res = dp1[i] + dp2[i];
        }
    }
    cout << n - (res - 1);
    return 0;
}