最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

给定一个长度为 $n$ 的数组 $a[n]$，表示第 $i$ 位同学的身高为 $a[i]$

题目要求我们从这个数组中删去一些小朋友，使得最终身高的顺序是先递增后递减

问最少删除多少个小朋友，可以构成想要的先递增后递减的序列

解析

这又是一个我们很熟悉的模型

为什么说很熟悉，因为在这个题解补全计划下，已经是第三次遇到他啦！

我直接 偷 用上一题的图了，不再另外画了

本题的要求是，我们对原数组删去尽量少的数字，构成该类型序列

我们知道，一个序列的子序列，就是通过删去原序列中部分的元素后构成的

因此，找到满足该类型序列，最少需要删除的元素数量 $\equiv$ 找到满足该类型序列，最长子序列的长度

通过这个等价转换，本题就完全转换成了上一题了

关于该类型题目的详细分析我都放在这篇博客里的AcWing 1014. 登山——状态机模型解决最长子序列问题

闫氏DP分析法也都在这篇的写过了，这里就不再额外写了，直接贴出代码

Code (最长上升子序列模型DP)

#include <iostream>

using namespace std;

const int N = 110;

int n;
int a[N];
int f_up[N], f_dw[N];

int main()
{
    //input
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    //从前往后找一遍最长上升
    a[0] = 0;
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 0; j < i; ++ j)
        {
            if (a[i] > a[j]) f_up[i] = max(f_up[i], f_up[j] + 1);
        }
    }
    //从后往前找一遍最长上升
    a[n + 1] = 0;
    for (int i = n; i; -- i)
    {
        for (int j = n + 1; j > i; -- j)
        {
            if (a[i] > a[j]) f_dw[i] = max(f_dw[i], f_dw[j] + 1);
        }
    }

    //find result from the final state
    int res = 0;
    for (int i = 1; i <= n; ++ i) res = max(res, f_up[i] + f_dw[i] - 1);
    cout << n - res << endl;

    return 0;
}

Code(状态机模型DP)

#include <iostream>

using namespace std;

const int N = 110;

int n;
int a[N];
int f[N][2];

int main()
{
    //input
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    //dp
    for (int i = 1; i <= n; ++ i)
    {
        f[i][0] = 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);
            if (a[i] < a[j]) f[i][1] = max(f[i][1], max(f[j][0], f[j][1]) + 1);
        }
    }

    //find result from final state
    int res = 0;
    for (int i = 1; i <= n; ++ i) res = max(res, max(f[i][0], f[i][1]));
    cout << n - res << endl;

    return 0;
}