P2516 [HAOI2010]最长公共子序列 题解

题目传送

Description

求两个字符串 \(a,b\) 的最长公共子序列以及出现次数。

Solution

看数据范围感觉是个 \(O(nm)\) DP，可是我不会写唉，那先把暴力搞出来吧。

设 \(f_{l,r}\) 表示第一个字符串匹配到 \(l\)，第二个字符串匹配到 \(r\)，并且子序列以 \(a_l,b_r\) 为结尾的最长长度。同时记录一个 \(g_{l,r}\) 表示出现次数。

可以推出一个比较显然的转移方程：

\[f_{l,r} = \max\{f_{i,j} + 1\}(1 \le i < l,1 \le j < r,a_i = b_j) \]

\[g_{l,r} = \sum_{i=1}^{l-1}\sum_{j=1}^{r-1}g_{i,j}(f_{l,r} = f_{i,j}+1) \]

考虑优化，观察这些状态从哪转移的。

假设我们现在更新 \(f_{l,r}\)。

我们需要知道什么？黄色矩阵中的最大值。

更新 \(g_{l,r}\) 呢，黄色矩阵中所有拥有最大值的 \(f_{i,j}\) 所对应的 \(g_{i,j}\) 的和。

所以我们可以设 \(Max_i = \max_{0\le x。

因为 \(Max_i\) 和 \(cnt_{i,y}\) 维护的都是 \(0 \sim l-1\) 行的情况，所以我们需要不断更新他们的值。

注意所有的这一行的信息都必须在这一行扫完后再更新。

在递推每一行时，记录一个 nowM 和 sum 分别表示到当前列之前的最大值，和最大值的出现次数。这样就可以把经过的每一列的信息合并在一起，方便更新 \(f_{l,r}\) 的值。

时间复杂度 \(O(n^2)\)。

开这么多二维数组一定会被卡空间。

我们发现 \(g_{l,r}\) 每次只需要存一行留着更新即可，前面的几行都没有用。

然后发现 \(f_{l,r}\) 在状态转移过程中根本没涉及到第一维什么事，直接压掉。

只留下一个二维数组，空间应该够用了。

但是我们发现 \(cnt_{i,y}\) 只会用到它这一列的最大值 \(Max_i\) 所对应的数。那么我们只对 \(cnt_{i,Max_i}\) 维护即可，又压掉一维！

几个注意的点：

• 更新时候的大前提 \(a_l=b_r\) 还是要保留的。
• 但是在记录 nowM 和 sum 时，不管两个字符是否相等都要更新。
• 如果你想给 \(f\) 初始化极小值，那么在 \(f_r < 0\) （压维后） 时就不要更新对应的 \(cnt_r\) 了。

Code

/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define LL long long
#define orz cout<<"lkp AK IOI!"<