题意

• 共有n个人，每个人有身高，移除若干人，使得序列为{纯升序||纯降序||先升序后降序}，求最少的移除人数

思路

• 方法1：对于整个序列正着求一个最长上升子序列，反着求一个最长上升子序列，枚举每个位置两个序列和，最大的减一即为序列最长长度。
• 方法2：维护一个二维dp数组，第二维记录当前元素属于升序列还是降序列，对于每个位置，如果他的值大于前面的某个值，则维护升序列，如果他的值小于，则维护降序列，特别的，维护降序列的时候，要比较作为降序列的开始还是衔接在前一个降序列，取两种情况中的最优解。
• 初值：对于每一个元素，至少都可以自己作为一个序列，所以所有初值为1。

PS

• 对于第二种方法，不需要在枚举每一个位置，答案要么是一个从头到尾的升序列，要么是先升后降的序列，通过给a[n+1]赋一个极小值来使得a[n+1]一定是先升后降的最后一个被选上的，那么这种情况的最大值就是

AC代码

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int n;
    cin >> n;
    int a[120]={0};
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    // 方法一：前后维护两个最长上升子序列
    int f1[120]={0},f2[120]={0};
    for(int i=1;i<=n;i++){
        f1[i]=1;
        for(int j=1;j<i;j++){
            if(a[i]>a[j]){
                f1[i]=max(f1[i],f1[j]+1);
            }
        }
    }
    for(int i=n;i>=1;i--){
        f2[i]=1;
        for(int j=n;j>i;j--){
            if(a[i]>a[j]){
                f2[i]=max(f2[i],f2[j]+1);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,f1[i]+f2[i]);
    }
    cout << n-(ans-1) << endl;
    //方法二：维护一个二维dp数组
    //第二维记录当前元素属于升序列还是降序列
    int f[120][2]={0};
    a[n+1]=-100;
    for(int i=1;i<=n+1;i++){
        f[i][0]=1;
        f[i][1]=1;
        for(int j=1;j<i;j++){
            if(a[i]>a[j]) f[i][0]=max(f[i][0],f[j][0]+1);
            else if(a[i]<a[j]) f[i][1]=max(f[i][1],max(f[j][0]+1,f[j][1]+1));
        }
    }
    // int ans=0;
    // for(int i=1;i<=n;i++){
    //     ans=max(ans,max(f[i][0],f[i][1]));
    // }
    cout << n-max(f[n+1][1]-1,f[n][0]) << endl;

    return 0;
}