CSP-J 2022 第一轮 第 23 题：程序（二）：f和g两行输出是否总相同

题目

1  #include <algorithm>
2  #include <iostream>
3  #include <limits>
4
5  using namespace std;
6
7  const int MAXN = 105;
8  const int MAXK = 105;
9
10 int h[MAXN][MAXK];
11
12 int f(int n, int m)
13 {
14     if (m == 1) return n;
15     if (n == 0) return 0;
16
17     int ret = numeric_limits<int>::max();
18     for (int i = 1; i <= n; i++)
19         ret = min(ret, max(f(n - i,m), f(i - 1, m - 1)) + 1);
20     return ret;
21 }
22
23 int g(int n, int m)
24 {
25     for (int i = 1;i <= n; i++)
26         h[i][1]= i;
27     for (int j = 1;j<= m; j++)
28         h[0][j]= 0;
29
30     for (int i= 1; i <= n; i++){
31         for (int j= 2; j <= m; j++){
32             h[i][j] = numeric_limits<int>::max();
33             for (int k = 1;k <= i;k++)
34             h[i][j]= min(
35                 h[i][j],
36                 max(h[i - k][j],h[k - 1][j - 1]) +1);
37         }
38     }
39
40     return h[n][m];
41 }
42
43 int main()
44 {
45     int n,m;
46     cin >> n>> m;
47     cout << f(n, m) << endl << g(n, m)<< endl;
48     return 0;
49 }

假设输入的n、m均是不超过100 的正整数，完成下面的判断题和单选题：

输出的两行整数总是相同的。

选项

• A. 正确
• B. 错误

答案

A

题解

答案：A. 正确。

关键是看出：g 用动态规划计算了和递归函数 f 相同的结果，也就是 h[n][m] = f(n,m)。

① 初始条件相同

f 的递归出口是：

``cpp f(n, 1) = n; f(0, m) = 0; ``

g 的初始化是：

``cpp h[i][1] = i; h[0][j] = 0; ``

两者完全对应。

② 计算公式相同

f(n,m) 枚举 i，取下面表达式的最小值：

``cpp max(f(n - i, m), f(i - 1, m - 1)) + 1 ``

g 计算 h[i][j] 时枚举 k，取：

``cpp max(h[i - k][j], h[k - 1][j - 1]) + 1 ``

只是变量名称不同，计算规则一致。

③ g 用到的状态都已经算好

这是最容易疑惑的地方：计算 h[i][j] 时，要用到 h[i-k][j]，虽然第二个下标仍然是 j，但由于 1 ≤ k ≤ i：

• i-k < i；
• k-1 < i。

所以这两个状态都在前面的行，已经计算完成；第 0 行也已经初始化。

因此，g 按行计算，逐步得到与 f 相同的结果，两行输出相同。