|
|
#include <bits/stdc++.h>
|
|
|
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;
|
|
|
} |
