CSP-J 2025 第一轮 第 28 题：程序（三）：给定输入时输出是否为 2

题目

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

当输入 4 1 2 3 4 1 3 2 2 时，输出为 2。（ ）

选项

• √. 正确
• ×. 错误

答案

√

题解

答案：√ 正确。

输入按顺序读入后：

• n = 4
• a = [1, 2, 3, 4]
• b = [1, 3, 2, 2]

程序求的是两个数组的最长公共子序列长度。子序列可以不连续，但元素的先后顺序不能改变。

f[i][j] 表示 a 的前 i 个元素与 b 的前 j 个元素的最长公共子序列长度：

• 可以跳过一个元素，取 f[i-1][j] 和 f[i][j-1] 的较大值。
• 如果 a[i] == b[j]，还可以把这个相同元素接在前面的公共子序列后面，取 f[i-1][j-1] + 1。

本题中，[1, 2] 和 [1, 3] 都是长度为 2 的公共子序列。

能否达到长度 3？由于 b 中没有 4，唯一可能是 [1, 2, 3]。但 b 中的 3 在所有 2 的前面，无法按顺序选出 [1, 2, 3]。

因此最长公共子序列长度是 2，程序输出 2。