CSP-J 2022 第一轮 第 27 题：程序（二）：输入100 100时的输出

题目

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 的正整数，完成下面的判断题和单选题：

（$4$ 分） 当输入 100 100 时，输出的第一行为（ ）。

选项

• A. $6$
• B. $7$
• C. $8$
• D. $9$

答案

B

题解

选 B，7。

关键看这一句： ``cpp max(f(n - i, m), f(i - 1, m - 1)) + 1 ` 它表示：选择位置 i，操作一次后有两种情况，剩余规模分别为 n-i 和 i-1。max 表示取最坏情况，外层 min 表示选择最优的 i`，让最坏情况下的操作次数尽量少。

当 m = 100 时，m 足够大，不会限制操作，可以每次选择中间位置，像二分查找一样缩小范围。

设最多操作 \(t\) 次能处理的最大规模为 \(S(t)\)。一次操作可以把问题分成两部分，因此： \[ S(0)=0,\qquad S(t)=2S(t-1)+1 \] 所以： \[ S(t)=2^t-1 \]

• 操作 6 次，最多处理 \(2^6-1=63\)；
• 操作 7 次，最多处理 \(2^7-1=127\)。

因为 \(63<100\le127\)，所以 f(100,100) = 7，第一行输出 7。

注意：这是按递归的数学结果作答；实际运行时，f 没有记忆化，会产生大量重复计算，耗时非常长。