发布时间：2023-03-17 17:30
// 1. dfs 顺序： 枚举可能的 r，h 拼成一层蛋糕 (顺序是层内操作)
// 2. dfs 状态： preR, preH, 当前层，累计体积，累计面经 (状态是分支和给下次的依赖值)
// (为什么穿入preR, preH 而不是 r，h？ 因为r，h不是固定值，是需要遍历的，穿入上层的值也只是作为题目要求的剪枝边界)
// 3. 剪枝：
// 3.1 优化搜索顺序：r，h ，level都从大到小搜索， 因为r^2 权重比h大，所以还有先搜索r
// 3.2 可行性剪枝：
// 3.2.1 & 3.2.2 ：累计超出最大体积；累计超出最小表面积；
// 原理是最小的r和h都是当前层数(1~m)，因为题中要求：当i < M时，要求Ri > Ri+1且 Hi > Hi+1
// 3.2.3 : 上下界 ：curR 上界为 r = Math.min(preR-1, (int)Math.sqrt(n-preV))， 下界为level
// curH 上界为 h = Math.min(preH-1, (n-preV)/r/r) ， 下界为 level
// 原理是 V = r^2 * h
// 3.3 最优化剪枝： 根据 表面积与体积不等式推导而出
// ================================
// 搜索状态：
// 搜索状态可视为一个多元组，每一维都是问题状态空间的一个维度，
// 在题目中，一般在“输入变量”， “限制条件”， “待求解变量”等关键位置体现
//
// 搜索剪枝：
// 1. 针对每个状态进行缩放对边界进行推导 (可行性)
// 2. 对未来的最小代价进行计算 (最优化)
import java.util.*;
public class Main{
void run(){
int n = jin.nextInt();
int m = jin.nextInt();
for(int i = 1 ;i <= m ; i++){
mins[i] = mins[i-1] + i*i*2;
minv[i] = minv[i-1] + i*i*i;
}
System.out.println(solve(n, m));
}
int solve(int n, int m){
// dfs2(n, (int)Math.sqrt(n), m, 0, 0, n, m);
dfs(Integer.MAX_VALUE, Integer.MAX_VALUE, m, 0, 0, n, m);
return res;
}
void dfs(int preR, int preH, int level, int preV, int preS, int n, int m){
if (preV + minv[level] > n) return ;
if (preS + mins[level] > res) return ;
if (preS + 2*(n-preV) / preR >= res) return ;
if (level == 0 ){
if (preV == n){
res = Math.min(res, preS);
}
return ;
}
for (int r = Math.min(preR-1, (int)Math.sqrt(n-preV)); r >= level; r--){
for (int h = Math.min(preH-1, (n-preV)/r/r); h >= level ;h--){
dfs(r, h, level-1, preV+r*r*h, preS+2*r*h+(level==m?r*r:0), n, m );
}
}
return ;
}
void dfs2 (int r, int h, int level, int preV, int preS, int n, int m){
if (level == 0 ){
if (preV == n){
res = Math.min(res, preS);
}
return ;
}
// int curV = r*r*h; // 错误原因是 这个是上一个的值
// int curS = 2*r*h; // 不能开始就认为 r,h 是本层的值，
// 因为本层的值有多种可能需要遍历，最初的时候没法传入，而认为是上一层的值可以传哨兵
// if (level == m-1) curS += r*r;
for (int i = r-1 ;i > 0 ; i--){
for (int j = h-1 ; j>0 ; j--){
// dfs2(i, j, level-1, preV+curV, preS+curS, n, m); // 其实这里传入的也是上一次的值
dfs2(i, j, level-1, preV+i*i*j, preS+2*i*j+(level==m?i*i:0), n,m);
}
}
}
private int[] mins = new int[22];
private int[] minv = new int[22];
private int res = Integer.MAX_VALUE;
private Scanner jin = new Scanner(System.in);
public static void main(String[] args) throws Exception {new Main().run();}
}