题目描述
7月17日是Mr.W的生日,ACM-THU为此要制作一个体积为$Nπ$的$M$层生日蛋糕,每层都是一个圆柱体。
设从下往上数第i层蛋糕是半径为$Ri$, 高度为$Hi$的圆柱。
当i < M时,要求$Ri > Ri+1$且$Hi > Hi+1$。
由于要在蛋糕上抹奶油,为尽可能节约经费,我们希望蛋糕外表面(最下一层的下底面除外)的面积$Q$最小。
令$Q = Sπ$ ,请编程对给出的N和M,找出蛋糕的制作方案(适当的$Ri$和$Hi$的值),使$S$最小。
除$Q$外,以上所有数据皆为正整数 。
输入格式
输入包含两行,第一行为整数$N(N <= 10000)$,表示待制作的蛋糕的体积为$Nπ$。
第二行为整数$M(M <= 20)$,表示蛋糕的层数为$M$。
输出格式
输出仅一行,是一个正整数$S$(若无解则S = 0)。
数据范围
$
1≤N≤10000,
1≤M≤20
$
样例
输入样例:
100
2
输出样例:
68
算法
(dfs暴力枚举 + 剪枝优化)
解题思路:
枚举顺序:
- 枚举每一层的R和H。
剪枝优化:
- 优化搜索顺序: 优先搜索体积大的蛋糕块,还有在枚举的时候R和H都要从大到小枚举。
- 最优性剪枝及可行性剪枝:1. 这里我们保存一个minv[u],以及mins[u],表示的是[1, u]的所有蛋糕块的最小体积以及最小表面积,如果当前u+1层的蛋糕块的表面积s + mins[u] >= ans(全局最优解)[最优性剪枝],体积v + minv[u] > N(总体积)[可行性剪枝],则直接返回。2. 有公式$S_{1-u} = \sum_{k=1}^{u} 2 \* R_{k} \* H_{k}$,$n - v = \sum_{k=1}^{u} R_{k} \* R_{k} \* H_{k}$,对第一个公式做一个变形得$\frac{2}{R_{u+1}} \* \sum_{k=1}^{u} R_{k} \* H_{k} \* R_{u+1}$,用第二个等式进行替换得,$S_{1-u} >= \frac{2 * (n-v)}{R_{u+1}}$,所以如果此时的$s + \frac{2 * (n-v)}{R_{u+1}} >= ans$,则可以直接返回, 这里$S_{1-u}$可以取到等号的原因是当n == v时,此时$S_{1-u}$和$\frac{2 * (n-v)}{R_{u+1}}$是相等的。[最优性剪枝]。
- 搜索边界剪枝:对于当前枚举到的蛋糕块u,此时已经用了v体积,那么对于剩下的n-v的体积,有不等式$R_{u} \* R_{u} \* H_{u} <= n - v$,由于$H_{u}$最小为1,所以$R <= \sqrt{n-v}$,又$R_{u} <= R_{u+1} -1$,故R的上界为$min(\sqrt{n-v}, R_{u+1} - 1)$,对于R的下界,从上往下,每一层的R都是递增的,故第u层的R的最小值应该为$u$,根据不等式$H_{u}$的上界也可以求出来为$\frac{n-v}{R^2}$,又$H_{u} <= H_{u+1} -1$,故$H_{u}$的上界为$min(\frac{n-v}{R^2}, H_{u+1} - 1)$,同理$H_{u} $的下界也为$u$。
时间复杂度
估计不出来QWQ
参考文献
算法提高课
java 代码
import java.io.*;
class Main{
static int N = 30, INF = 0x3f3f3f3f;
static int[] minv = new int[N];
static int[] mins = new int[N];
static int[] R = new int[N]; // 存储每一层的R
static int[] H = new int[N]; // 存储每一层的H
static int n, m;
static int ans = INF;
static void dfs(int c, int v, int s){
if(v + minv[c] > n) return;
if(s + mins[c] >= ans) return;
if(s + (n - v) / R[c+1] * 2 >= ans) return;
if(c == 0){
if(v == n) ans = s;
return;
}
for(int r=Math.min(R[c+1]-1, (int)Math.sqrt(n-v)); r>=c; r--){
for(int h=Math.min(H[c+1]-1, (n-v)/r/r); h>=c; h--){
if(v + r * r * h <= n){
int t = 2 * r * h;
if(c == m) t += r * r;
R[c] = r; H[c] = h;
dfs(c-1, v + r * r * h, s + t);
}
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(in.readLine());
m = Integer.parseInt(in.readLine());
for(int i=1; i<=m; i++) {
minv[i] = i * i * i;
mins[i] = 2 * i * i;
}
R[m+1] = INF; H[m+1] = INF;
dfs(m, 0, 0);
if(ans == INF) System.out.println(0);
else System.out.println(ans);
}
}