CSP-J 2025 第一轮 第 33 题：程序（三）：a=1..n 时代码等价于什么问题

题目

#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;
}

（本题在原卷中被删除）如果输入的 $a = \{1, 2, \dots, n\}$，而且 $b$ 数组中数字均为 $1 \sim n$ 中的正整数，则上述代码等价于下面哪个问题：（ ）。

选项

• A. 求 $b$ 数组去重后的长度
• B. 求 $b$ 数组的最长上升子序列
• C. 求 $b$ 数组的长度
• D. 求 $b$ 数组的最大值

答案

B

题解

答案是 B：求 \(b\) 数组的最长上升子序列的长度，这里的“上升”指严格递增。

这段代码求的是两个数组的最长公共子序列（LCS）长度。令 \(f[i][j]\) 表示 \(a\) 的前 \(i\) 个元素与 \(b\) 的前 \(j\) 个元素的最长公共子序列长度：

• 不选 \(a[i]\) 或不选 \(b[j]\)，得到 \(\max(f[i-1][j], f[i][j-1])\)。
• 当 \(a[i]=b[j]\) 时，可以把它接在之前的公共子序列后面，得到 \(f[i-1][j-1]+1\)。

当 \(a=\{1,2,\dots,n\}\) 时：

1. 公共子序列一定严格递增，因为它必须按照 \(a\) 中的顺序出现。
2. \(b\) 的任何严格递增子序列都是公共子序列，因为其元素都在 \(1\sim n\) 内，且在 \(a\) 中也按相同顺序出现。

因此，最长公共子序列的长度，就是 \(b\) 的最长严格上升子序列的长度。

例如，\(a=[1,2,3,4]\)，\(b=[3,1,2,2]\)，最长上升子序列为 \([1,2]\)，输出 2；去重后有 3 个数，所以不是 A。

注意：子序列可以不连续，但不能改变原来的先后顺序。