题解 | #合唱队形#

从右往左 求最大递增子序列 从左往右求最大递增子序列

合并在一起 去除中间同学 得到山丘型的序列答案

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 1010;
int a[N], f[N], g[N];

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    for(int i = 0; i < n; i ++){
        f[i] = 1;
        for(int j = 0; j < i; j ++){
            // 递增
            if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
        }
    }

    // 从右往左求最大上升子序列 也就是最大递减序列的长度
    for(int i = n - 1; i >= 0; i --){
        g[i] = 1;
        for(int j = n - 1; j > i; j --){
            if(a[i] > a[j]) g[i] = max(g[i], g[j] + 1);
        }
    }

    int res = 0;
    // f[i]是以i为终点的最大上升子序列 g[i]是以i为起点的递减子序列
    for(int i = 0; i < n; i ++) res = max(res, f[i] + g[i] - 1);

    res = n - res;
    cout << res;
}