Oiclass P1241 题解

这次是 LIS 的兄弟 LCS（最长公共子序列）

一个词概括，模板题。但是，模板题也很难啊啊啊啊啊啊。又是经典的五步：

1. 划分状态

假设 \(a\) 和 \(b\) 是本次主角字符串（好想把他们拉出去斩了） ，那么一共有 \(a.length() \times b.length()\) 种状态，每一种状态表示下标 \(i\) 之前的 \(a\) 的子串（即 a.substr(0, i)）与下标 \(j\) 前的 \(b\) 的子串（即 b.substr(0, j)）的最长公共子序列的长度。

2. 确定状态和状态变量

状态就是 （1） 里面说的，那么状态变量我用一个二维数组 \(f\) ，也就是说 \(f_{i,\ j}\) 就是一个表示下标 \(i\) 之前的 \(a\) 的子串（即 a.substr(0, i)）与下标 \(j\) 前的 \(b\) 的子串（即 b.substr(0, j)）的最长公共子序列的长度的状态

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

决策很简单呢，如果相同，那么就 \(+1\) 如果不同，那么就选择复制 \(f_{i-1,\ j}\) 和 \(f_{i,\ j-1}\) 中大的那一个，很简单，写出方程如下： \[ f_{i,\ j} = \left\{ \begin{array}{lr} a_i = b_j\ \ \ \ f_{i - 1,\ j-1} + 1\\ a_i ≠ b_j\ \ \ \ \max(f_{i-1,\ j},\ f_{i,\ j-1}) \end{array} \right. \]

4. 初始值

初始值想都不用想，全都是 蛋（\(0\)），那么也就很简单了，什么都不用干，只需要创建数组，完事儿

5. 实现

实现直接模拟就可以 AC，注意一点，如果想我一样图方便把循环的原始值设置成 \(0\) 的话，会有一个问题，你在继承值的时候涉及到 \(-1\) 的操作，这就会导致数组越界，轻则算不准，重则 RE \(0\ pts\) ，避完坑之后就可以放心打代码了，如下：

#include <iostream>

using namespace std;

int f[2009][2009];
string a, b;

int main() {
    cin >> a >> b;
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            if (a[i - 1] == b[j - 1]) {
                f[i][j] = f[i - 1][j - 1] + 1;
            } else {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }
        }
    }
    cout << f[a.length()][b.length()];
}