Oiclass P1226 题解

话不多说，这又是一道 DP 题

看题目就知道，这就是大名鼎鼎的最长不下降子序列 LIS 。所以我们用十分传统的五步（第六步是送的）解决这个问题

1. 划分阶段

我们的以每一个数划分阶段，也就是说每一个阶段存储的是以某个数结尾的子序列

2. 确定状态和状态变量

这里使用数组 \(f\) 来存放状态，数组 \(a\) 存储输入的数据，即状态 \(f_i\) 为以数字 \(a_i\) 结尾的最长不下降子序列的长度。

3. 确定决策并写出状态转移方程

对于数字 \(a_i\) 他可以与位于他前面的任何一个数连在一起形成一个子序列，当然了，如果 \(a_i\) 嫌弃前面的子序列态太短，他也可以自己形成一个新的子序列，使得他自己所在的子序列是最短的，基于这些分析，我们可以写出以下状态转移方程： \[ f_i = \max\left(\max_{j\ = \ 1,\ j++}^{0\ <\ j\ <\ i} ,\ f_i\right) \]

4. 寻找边界条件

因为每一个数字都可以成为一个单独的子序列，所以边界条件就是所有的数字代表的状态都是 \(1\) 也就是说： \[ f_i = 1\ \ (0\ <\ i\ ≤\ n)\ n为数组长度 \]

5. 实现

实现非常简单，只需要在输入的时候把边界条件赋值，然后用状态转移公式计算出每一个状态在取所有状态的最大值输出就可以了，代码如下：

#include <iostream>

using namespace std;

int n, a[1009], f[1009], ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        f[i] = 1;
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (a[j] <= a[i]) {
                f[i] = max(f[i], f[j] + 1);
                ans = max(f[i], ans);
            }
        }
    }
    cout << ans;
}

6. 送的

如果你都看到这里了，说明你对 LIS 很感兴趣，那么相信你也对我写的题解很感兴趣吧（疯狂暗示点赞）。

有些友好的题目可能会要求你输出这个最长不下降子序列，那么这个时候要怎么办呢？如果你写过需要输出路径的深搜（DFS）或者广搜(BFS) 那么你可能会有一些思路，毕竟原理差不多。在这里，我们需要定义一个数组，用来存储第 \(i\) 个数字的上一个数字（可以理解为指针），这里我使用数组 \(pre\) 对于 \(pre\) 的初始值，我将其设置为 \(-1\) （后面会讲到为什么）在我进行状态的转移的时候，例如状态 \(f_i\) 假设 $f_i $ 的要转移的一项是 \(f_j\) 那么 \(pre_i=j\) 。OK，那么怎么输出呢？我们可以写一个递归函数，获得上一项的位置后对自己进行递归调用，等到发现自己的值是 \(-1\) 时（\(pre_{self}=-1\)）return 那么就可以解决输出的问题，这也是为什么要把数组里每一项的初始值都设为 \(-1\) 这样就可以有效输出了。好，接下来看一看代码吧：

#include <iostream>

using namespace std;

int n, p, a[1009], f[1009], pre[1009], ans;

void print(int x) {
    if (pre[x] == -1) {
        cout << a[x] << " ";
        return;
    }
    print(pre[x]);
    cout << a[x] << " ";
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        f[i] = 1;
        pre[i] = -1;
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (a[j] <= a[i]) {
                if (f[i] < f[j] + 1) {
                    pre[i] = j;
                    f[i] = f[j] + 1;
                }
            }
        }
        if (ans < f[i]) {
            p = i;
            ans = f[i];
        }
    }
    cout << ans << endl;
    print(p);
}

是不是很妙？