学进去

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   的 正整数 ，完成下面的判断题和单选题 ：
判断题
（1）当输入为“7 3”时，第19行用来取最小值的min函数执行了449次。(     )
（2）输出的两行整数总是相同的。(     )
（3）当m为1时，输出的第一行总为n。(     )
单选题
（4）算法g（n，m）最为准确的时间复杂度分析结果为(     )。
A. 0(n^3/2m)              B. 0(nm)              C. 0(n²m)              D. 0(nm²)
（5）当输入为“20 2”时，输出的第一行为(     )。
A.“4”              B.“5”              C.“6”              D.“20”
（6）当输入为“100   100”时，输出的第一行为(     )。
A.“6”              B.“7”              C.“8”              D.“9”