1 #include <algorithm>2 #include <iostream>3 #include <limits>45 using namespace std;67 const int MAXN = 105;8 const int MAXK = 105;910 int h[MAXN][MAXK];1112 int f(int n, int m)13 {14 if (m == 1) return n;15 if (n == 0) return 0;1617 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 }2223 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;2930 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 }3940 return h[n][m];41 }4243 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 的正整数,完成下面的判断题和单选题:
判断题
当输入为 7 3 时,第 行用来取最小值的 min 函数执行了 次。
输出的两行整数总是相同的。
当 为 时,输出的第一行总为 。 单选题
算法 最为准确的时间复杂度分析结果为( )。
当输入为 20 2 时,输出的第一行为( )。
( 分) 当输入 100 100 时,输出的第一行为( )。