CSP-J 2025 第一轮 第 29 题：程序（三）：是否任意 f[i][j]≤f[n][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;
}

当程序运行完毕后，对于所有的 $1 \leq i, j \leq n$，都一定有 $f[i][j] \leq f[n][n]$。（ ）

选项

• √. 正确
• ×. 错误

答案

√

题解

答案是 √，正确。

关键是看状态转移中的这一句：

``cpp f[i][j] = std::max(f[i][j], std::max(f[i - 1][j], f[i][j - 1])); ``

它保证计算完当前格子后，一定有：

\[ f[i][j] \ge f[i-1][j],\qquad f[i][j] \ge f[i][j-1]. \]

后面的 if 语句也通过 max 更新，因此只可能让当前值增大，不会破坏这两个不等式。又因为程序按行、按列从小到大计算，当前格子的上方和左方都已经计算完成，所以这些不等式在程序结束后仍然成立。

因此，在数组 f 中向下或向右走，数值都不会减小。从任意位置 (i,j) 出发，先向下走到 (n,j)，再向右走到 (n,n)，就得到：

\[ f[i][j] \le f[n][j] \le f[n][n]. \]

这就证明了题目中的结论。

也可以从算法含义理解：f[i][j] 表示 a 的前 i 个元素与 b 的前 j 个元素的最长公共子序列长度。把两个序列的范围扩大到完整的长度 n 后，原来的公共子序列仍然存在，所以最长公共子序列的长度不会变小。