您现在的位置是：首页 >其他 >生日蛋糕 dfs 剪枝网站首页其他

? 算法题解专栏

? 生日蛋糕

$7$ 月 $17$ 日是 Mr.W 的生日，ACM-THU 为此要制作一个体积为 $N\pi$ 的 $M$ 层生日蛋糕，每层都是一个圆柱体。

设从下往上数第 $i$ 层蛋糕是半径为 $R\_i$，高度为 $H\_i$ 的圆柱。

当 $i<M$ 时，要求 $R\_i>R\_i+1$ 且 $H\_i>H\_i+1$。

由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积 $Q$ 最小。

令 $Q=S\pi$ ，请编程对给出的 $N$ 和 $M$，找出蛋糕的制作方案（适当的 $R\_i$ 和 $H\_i$ 的值），使 $S$ 最小。

除 $Q$ 外，以上所有数据皆为正整数。

输入格式

输入包含两行，第一行为整数 $N$，表示待制作的蛋糕的体积为 $N\pi$。

第二行为整数 $M$，表示蛋糕的层数为 $M$。

输出格式

输出仅一行，是一个正整数 $S$（若无解则 $S=0$）。

数据范围

$1\le N\le 10000$,
$1\le M\le 20$

输入样例：

100
2	

输出样例：

68

? 思路待补

package acwing.搜索.DFS;

import java.util.Scanner;

public class 生日蛋糕
{
	static int N = 10010;
	static int n, m, INF = 0x3f3f3f3f;
	static int[] minv = new int[30];
	static int[] mins = new int[30];
	static int[] H = new int[30];// 记录每一层的高度
	static int[] R = new int[30];// 记录每一层的半径
	static int ans = INF, s, v;

	/**
	 * @param u 当前层数
	 * @param v 当前体积和
	 * @param s 当前面积和
	 */
	static void dfs(int u, int v, int s)
	{
		if (v + minv[u] > n)
			return;
		if (s + mins[u] >= ans)
			return;
		if (s + (2 * (n - v) / R[u + 1]) >= ans)
			return;

		if (u == 0)
		{
			if (v == n)
				ans = s;
			return;
		}
//																
		for (int r = Math.min((int) Math.sqrt(n - v), R[u + 1] - 1); r >= u; r--)
		{
			for (int h = Math.min((n - v) / r / r, H[u + 1] - 1); h >= u; h--)
			{
				int t = 0;
				if (u == m)
					t = r * r;
				R[u] = r;
				H[u] = h;
				dfs(u - 1, v + (r * r * h), s + (2 * r * h) + t);
			}
		}

	}

	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		for (int i = 1; i <= m; i++)
		{
			minv[i] = minv[i - 1] + i * i * i;
			mins[i] = mins[i - 1] + i * i;
		}
		H[m + 1] = INF;
		R[m + 1] = INF;
		dfs(m, 0, 0);
		if (ans == INF)
			System.out.println("0");
		else
			System.out.println(ans);
	}
}