CSP-J 入门级 · CSP 2025 入门级第一轮 第 18 题

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int f[5007][5007];
int a[5007], b[5007];
int n;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &b[i]);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            f[i][j] = std::max(f[i][j], std::max(f[i - 1][j], f[i][j - 1]));
            if (a[i] == b[j]) {
                f[i][j] = std::max(f[i][j], f[i - 1][j - 1] + 1);
            }
        }
    }
    printf("%d\n", f[n][n]);
    return 0;
}

判断题

28. 当输入 4 1 2 3 4 1 3 2 2 时，输出为 2。（ ） 29. 当程序运行完毕后，对于所有的 $1 \leq i, j \leq n$，都一定有 $f[i][j] \leq f[n][n]$。（ ） 30. 将第 18 行的 f[i][j] = std::max(f[i][j], std::max(f[i-1][j], f[i][j-1])); 删去后，并不影响程序运行结果。（ ）

单选题

31. 输出的答案满足的性质有（ ）。 A. 小于等于 $n

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考的是经典的最长公共子序列（LCS）DP。拿到题先别急着看选项，盯着代码里那个二维数组 f 的转移方程：先继承左边或上边的最大值，再判断当前字符是否相等，相等时加上左上角的值。这就是 LCS 的标准写法，把 a 和 b 看作两个序列，f[i][j] 存的就是 a[1..i] 和 b[1..j] 的 LCS 长度。

最容易掉进第 30 题的坑：以为去掉那行 max 继承代码不影响结果。其实那行是必须的——当 a[i]≠b[j] 时，如果不继承 f[i-1][j] 或 f[i][j-1]，f[i][j] 就会死死停在 0（因为初始化全是 0），导致整个表格后面全错。另外，第 33 题容易混淆 LCS 和 LIS 的条件：只有当 a 本身是严格递增序列时，LCS(a,b) 才等价于 b 的 LIS；如果 a 不是递增的，这个结论就不成立了。

考点定位

这是一道典型的最长公共子序列（LCS）动态规划题，同时考察了 DP 表格的单调性、状态转移的必要性，以及 LCS 与 LIS 的等价转化条件。

核心概念：什么是 LCS？

• 子序列：从原序列中删掉若干字符（可以不删），剩下的保持原顺序。比如 "AC" 是 "ABC" 的子序列，但 "AC" 不是 "ABC" 的子串（子串必须连续）。
• LCS：同时是两个序列的子序列中，最长的那个。例如 a=[1,2,3,4], b=[1,3,2,2]，它们的 LCS 可以是 "13" 或 "12"，长度都是 2。
• DP 状态：f[i][j] 表示 a 的前 i 个元素和 b 的前 j 个元素的 LCS 长度。
• 转移方程：

1. 先继承：f[i][j] = max(f[i][j], f[i-1][j], f[i][j-1]) —— 当前点至少能取到左边或上边的结果。 2. 再判断：如果 a[i] == b[j]，说明这两个字符可以一起加入子序列，于是 f[i][j] = max(f[i][j], f[i-1][j-1] + 1)。

命题人怎么挖坑？

1. 第 30 题的陷阱：去掉那行 max(f[i][j], f[i-1][j], f[i][j-1]) 后，当 a[i]≠b[j] 时，f[i][j] 永远保持 0（因为数组全局初始化就是 0，且没有 else 分支给它赋值）。结果整个表格全错，输出自然错。不是“不影响”，而是“必错”。 2. 第 33 题的等价条件：很多人看到 a 是 1..n 就以为 LCS 一定等于 LIS，其实必须同时满足：a 是递增序列 且 b 中的元素都在 1..n 范围内（题目已给）。此时 LCS(a,b) 中的公共部分在 a 中必然是递增的，所以 LCS 长度就等于 b 的最长上升子序列长度。 3. 第 32 题的排序影响：在循环前对 a、b 排序，相当于把两个序列里的相同数字按顺序排好。LCS 只关心“有没有”和“顺序”，不关心“重复多少次”，所以排序只会让某些原本分散的匹配变成连续匹配，LCS 长度变大或不变，绝不会变小。

逐题推演

第 28 题：输入 4 1 2 3 4 1 3 2 2

a = [1,2,3,4], b = [1,3,2,2]。 手动画表（n=4）：

f[4][4]=2，LCS 为 "13" 或 "12"。答案 正确。