#include using namespace std; const int INF = 0x3f3f3f3f; const int N = 22; int n; // 待制作的蛋糕的体积为 int m; // 蛋糕的层数为 m int ans = INF; // 最小表面积,预求最小,先设最大 int mins[N]; // 每一层的最小表面积 int minv[N]; // 每一层的最小体积 int R[N], H[N]; // 为每一层蛋糕分配的半径和高度 // u:正在研究第几层 // v:已经使用了的体积 // s:已经使用了的表面积 void dfs(int u, int v, int s) { // 如果来到第u层,发现,已经使用过的体积v,加上第1~u层最小体积minv[u] ,大于整体的体积n,就不用再继续了 if (v + minv[u] > n) return; // 如果来到第u层,发现,已经使用过的表面各s,加上第u层及以上所有层需要的表面积mins[u] // 大于当前最优解了,就不用再继续研究了,还不如最优解,再研究也是白扯 if (s + mins[u] >= ans) return; // 第二个最优性剪枝,侧面积和体积不是孤立存在的,是有关联关系的。 // 不符合这个关联关系的Ri和Hi是没有必要继续的 if (2 * (n - v) / R[u + 1] + s >= ans) return; // 摆完所有层蛋糕 if (u == 0) { // 如果已经使用的体积等于n,如果是,那么更新答案 if (v == n) ans = s; return; } // 枚举每一个可能的半径,同理,半径由大到小 for (int r = min(R[u + 1] - 1, (int)sqrt((n - v) / u)); r >= u; r--) for (int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; h--) { // 如果是第m层,需要加上一个底面积,其它层就只计算侧面积 int t = (u == m ? r * r : 0); // 记录下第u层的选择,半径:r,高度:h R[u] = r, H[u] = h; // 因为静态数组可以重复按索引写入,所以不需要回溯 // 递归上一层,体积变为v+r*r*h,表面积由s变大为 s + 2 * r * h + t dfs(u - 1, v + r * r * h, s + 2 * r * h + t); } } int main() { cin >> n >> m; // 预处理 for (int i = 1; i <= m; i++) { // 第i层,半径最小是i,高度最小是i,否则更小层无法获得整数解 // 预处理出每层及上边所有层的最小表面积,看清楚这是一个叠加的关系,不是简单的计算,是递推式 mins[i] = mins[i - 1] + 2 * i * i; // 预处理出每层及上边所有层的最小体积 minv[i] = minv[i - 1] + i * i * i; } // 初始化为无穷大,防止在计算下层半径高度时取到0 R[m + 1] = H[m + 1] = INF; // 从下向上进行深搜,按经验来看,这样能减少出发时的分枝数量,效率提升 // 从m层出发,此时的体积为0,此时的表面积为0 dfs(m, 0, 0); // 输出答案 if (ans == INF) puts("0"); else printf("%d\n", ans); return 0; }