---
title: "非递减子序列拓展思路"
created: 2025-11-28
tags:
  - 算法
---

# 非递减子序列拓展思路

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

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

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

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

![[image-3a2f15e2.png]]

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

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

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

闫氏DP分析法

![[image-c06ed128.png]]

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

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

想更近一步了解这类模型的话，可以做一下这道题 [AcWing 3549. 最长非递减子序列](https://www.acwing.com/problem/content/3552/)

```cpp
#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-刷题理模型]] ➡️ [[编辑距离|编辑距离]]