AcWing 168. 生日蛋糕(Java)
原题链接
中等
作者:
上杉
,
2021-05-29 16:07:29
,
所有人可见
,
阅读 451
import java.util.Scanner;
/**
* @program: 算法题
* @author: 上杉
* @create: 2021-05-29 14:44
**/
public class Main {
static int N;//蛋糕的体积为N,r1*r1*h1 + r2*r2*h2 +...
static int M;//蛋糕限制为M层
static int[] minV;
static int[] minS;
static int res = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
N = input.nextInt();M = input.nextInt();
minV = new int[M+1];
minS = new int[M+1];
for (int i = 1; i <= M; i++) {
minV[i] = minV[i-1] + i * i * i;
minS[i] = minS[i-1] + 2 * i * i;
}
dfs(Integer.MAX_VALUE,Integer.MAX_VALUE,0,0,0);
System.out.println(res == Integer.MAX_VALUE ? 0 : res);
}
private static void dfs(int preR, int preH, int dep, int curS, int curV) {
if (dep == M ){
if (N == curV){
res = Math.min(res,curS);
}
return;
}
if (curS + minS[M-dep] > res)return;
if (curV + minV[M-dep] > N) return;
if (2 * (N - curV) / preR + curS > res) return;
//r*r*h
int r = Math.min(preR - 1,(int) Math.sqrt(N-curV));
for (; r >= M - dep; r--) {
int h = Math.min(preH - 1,N);
for (;h >= M - dep;h--){
int s = 2 * r * h + (dep == 0 ? r * r : 0);
int v = r * r * h;
dfs(r,h,dep+1,curS+s,curV + v);
}
}
}
}