题解 | #合唱队形#

关键找 第i个，1~i 是一种递增的顺序， i~k是递减的顺序

最少几位出列： 找一个i 使得递增序列的长度和递减序列的长度 和最大

那就枚举 每个i 作为那个 队形中 最高值的情况。

这样i之前就是 求以h[i]为结尾的最长递增子序列的长度，就是求一遍数组的最长子序列，对应的f[i]自然就表示了“h[i]为结尾的最长递增子序列的长度”

#include <iostream>
using namespace std;
const int N = 1000;
int h[N];
int f[N];  //f[i]表示 以i为结尾的 最长上升子序列的长度
int g[N];   //g[i]表示 以i为开始的 最长下降子序列的长度

/*
关键找 第i个，1~i 是一种递增的顺序， i~k是递减的顺序
最少几位出列： 找一个i 使得递增序列的长度和递减序列的长度 和最大
那就枚举 每个i 作为那个 队形中 最高值的情况，
*/

int main() {
    int maxD = 1;
    int maxU = 1;
    int n;
    cin >> n;
    for(int i = 1;i<=n;i++){
        cin >> h[i];
    }
    for(int i = 1;i<=n;i++){
        f[i] = 1;
        for(int j = 1;j<i;j++){
            if(h[j]<h[i]){
                f[i] = max(f[i], f[j]+1);
            }
        }
    }
    //这里要从后往前遍历
    for(int i = n;i>0;i--){
        g[i] = 1;
        for(int j = n;j>i;j--){
            if(h[j]<h[i]){
                g[i] = max(g[i], g[j]+1);
            }
        }
    }

    int res = 0;
    for(int i = 1;i<=n;i++){
        res = max(res, f[i]+g[i]-1);
    }
    cout << n-res << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")