
```
01 #include <algorithm>
02 #include <iostream>
03 #include <limits>
04
05 using namespace std;
06
07 const int MAXN = 105;
08 const int MAXK = 105;
09
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 的正整数，完成下面的判断题和单选题：

判断题
22.当输入为“7 3”时，第 19 行用来取最小值的 min 函数执行了 449 次。（ ）
23.输出的两行整数总是相同的。（ ）
24.当 m 为 1 时，输出的第一行总为 n。（ ）

单选题
25. 算法 g(n,m)最为准确的时间复杂度分析结果为（ ）。
![image.png](https://ydschool-video.nosdn.127.net/1663485020202image.png)

26.当输入为“20 2”时，输出的第一行为（ ）。
A. “4”
B. “5”
C. “6”
D. “20”
27. （4 分）当输入为“100 100”时，输出的第一行为（ ）。
A. “6”
B. “7”
C. “8”
D. “9”



`答题须知`
1.判题时**不**忽略大小写，如答案为B，而你输入的答案为b，则会被判错！
2.判题时**不**会忽略你输入答案的前后空格，如答案为B，而你输入的答案为空格B空格，则会被判错！
3.**判断题 A代表正确、B代表错误**
</br>


有道小图灵信息学

动态规划

有道小图灵 信息学

动态规划

有道小图灵信息学