非递减子序列拓展思路

我这里给一个不同的思路这是我做过 AcWing第二场热身赛的C题——AcWing 3549. 最长非递减子序列后总结出来的一类模型

那就是，利用状态机模型DP解决最长xxx子序列模型的方法

xxx可以是先上升后下降，或者先上升后下降再上升，或者先上升后下降再上升再下降 ···

回到本题，我们就可以先利用状态机模型进行分析，具体如下：

对于本题来说，当前状态如果是上升状态，则他下一个阶段可以维持上升状态，或者变成下降状态

而对于已经处于下降状态来说的状态，下一个阶段只能继续维持下降状态

于是我们便可以写出状态机模型的闫氏DP分析法：

闫氏DP分析法

初始状态: f[0][0]和f[0][1]

目标状态: f[i][0]和f[i][1]

想更近一步了解这类模型的话，可以做一下这道题 AcWing 3549. 最长非递减子序列

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n;

int a[N];

int f[N][2];

int main()

{

    cin >> n;

    for (int i = 1; i <= n; ++ i)

        cin >> a[i];

    for (int i = 1; i <= n; ++ i)

    {

        f[i][0] = f[i][1] = 1;

        for (int k = 1; k < i; ++ k)

        {

            if (a[k] < a[i])

                f[i][0] = max(f[i][0], f[k][0] + 1);

            if (a[k] > a[i])

                f[i][1] = max(f[i][1], max(f[k][0], f[k][1]) + 1);

        }

    }

    int res = 0;

    for (int i = 1; i <= n; ++ i)

        res = max(res, max(f[i][0], f[i][1]));

    cout << res << endl;

    return 0;

}

⬅️ 登山 🏠 00-刷题理模型 ➡️ 编辑距离

非递减子序列拓展思路

💬 评论