#1463. 2022年阅读第二题
2022年阅读第二题
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 的正整数,完成下面的判断题和单选题: 判断题 1.当输入为 7 3 时,第 19 行用来取最小值的 min 函数执行了449 次。{{ select(1) }}
- 正确
- 错误
2.输出的两行整数总是相同的。{{ select(2) }}
- 正确
- 错误
3.当m为1时,输出的第一行总为n。{{ select(3) }}
- 正确
- 错误
单选题 4.算法 g(n,m) 最为准确的时间复杂度分析结果为( )。{{ select(4) }}
- O(m)
- O(nm)
- O(m)
- O(n)
5.当输入为 20 2 时,输出的第一行为( )。{{ select(5) }}
- 4
- 5
- 6
- 20
6.当输入 100 100 时,输出的第一行为( )。{{ select(6) }}
- 6
- 7
- 8
- 9