#include <algorithm> #include <iostream> #include <limits> using namespace std; const int MAXN = 105; const int MAXK = 105; int h[MAXN][MAXK]; int f(int n, int m) { if (m == 1) return n; if (n == 0) return 0; int ret = numeric_limits<int>::max(); for (int i = 1; i <= n; i++) ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1); return ret; } int g(int n, int m) { for (int i = 1; i <= n; i++) h[i][1] = i; for (int j = 1; j <= m; j++) h[0][j] = 0; for (int i = 1; i <= n; i++) { for (int j = 2; j <= m; j++) { h[i][j] = numeric_limits<int>::max(); for (int k = 1; k <= i; k++) h[i][j] = min( h[i][j], max(h[i - k][j], h[k - 1][j - 1]) + 1); } } return h[n][m]; } int main() { int n, m; cin >> n >> m; cout << f(n, m) << endl << g(n, m) << endl; return 0; }

这段代码的功能是计算将 n 个元素划分成 m 个部分所需的最小代价，代价的计算方式是每个部分的代价是该部分中元素的最大值加1，且要求每个部分中至少有一个元素。

其中，函数 f(n, m) 使用递归的方式计算最小代价，函数 g(n, m) 使用动态规划的方式计算最小代价，并且使用一个二维数组 h 来存储已经计算过的值，避免重复计算。

在 main 函数中，先读入 n 和 m，然后分别调用 f(n, m) 和 g(n, m) 计算最小代价，并将结果输出。

相关问题

#include <iostream> #include<algorithm> #include<cmath> #include <queue> using namespace std;

#include <iostream>：这是C++标准库中的头文件，用于输入输出流操作，包括cin、cout等。

#include<algorithm>：这是C++标准库中的头文件，用于提供各种算法操作，如排序、查找等。

#include<cmath>：这是C++标准库中的头文件，用于提供数学函数操作，如绝对值、平方根等。

#include <queue>：这是C++标准库中的头文件，用于提供队列操作，包括入队、出队等。

using namespace std;：这是C++的命名空间声明，表示使用std命名空间，可以直接使用std中的函数和对象。

#include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; s

这段代码是C++语言中的头文件引入部分，用于在程序中引入iostream、vector、algorithm和queue等库，以便使用这些库中的函数和类。其中，iostream库提供了C++输入输出流的功能，vector库提供了可变大小的数组容器，algorithm库提供了常用的算法函数，queue库提供了队列容器的支持。通过这些库，可以方便地进行程序开发和数据处理。