一 问题描述

制作一个体积为 Nπ 的 M 层生日蛋糕，每层都是一个圆柱体。设从下往上数第 i 层蛋糕是半径 Ri、高度为 Hi 的圆柱。当 i < M 时，要求 Ri > Ri+1 且 Hi > Hi+1。由于要在蛋糕商抹奶油，所以为了尽可能节约经费，希望蛋糕外表面面积 Q 最小。令 Q = Sπ,对给出的 N 和 M，找出蛋糕的制作方案，使 S 最小。除了 Q 外，以上所有数据皆为正整数。

二 输入和输出

1 输入

输入包含两行，第 1 行为 N，表示制作蛋糕的体现为 N π；第 2 行为 M，表示蛋糕的层数。

2 输出

单行输出一个正整数 S（若无解，则 S = 0）

三 输入和输出样例

1 输入样例

100

2

2 输出样例

68

四 分析

本问题在体积和层数一定的情况下，找到合适的半径和高度，使蛋糕表面积最小。可以使用回溯法搜索求解。

五 算法设计

1 预处理

从顶层向下计算出最小体积和面积的最小可能值。在从顶层（即第1层）到第 i 层的最小体积 minv[i] 成立时，第 i 层的半径和高度都为 i。此时只计算侧面积，对上表面积只在底层计算一次，底层的底面积即总的上表面积。

2 算法设计

dep 指当前深度；sumv、sums 分别指当前体积和、面积和；r、h 分别指当前层半径、高度。

a 从底层 m 层向上搜索，当 dep =0，搜索完成，更新最小面积。

b 剪枝技巧

• 如果当前体积加上剩余上面几层的最小体积大于总体积 n，则退出。
• 如果当前面积加上剩余上面几层的最小面积大于最小面积，则退出。
• 如果当前面积加上剩余上剩余面积（剩余体积折算）大于最小面积，则退出。

c 枚举半径 i,按递减顺序枚举 dep 层蛋糕半径的每一个可能值 i，第 dep 层的半径最小为 dep

• 如果 dep=m，sums=i * i，底面积作为外表面积的初始值。
• 计算最大高度 maxh，即 dep 层蛋糕高度的上限，（n-sumv-minv[dep-1]）表示第 dep 层的最大体积。
• 枚举高度 j，按递减顺序枚举 dep 层高度的每一个可能值 j,第 dep 层的最小高度为 dep。
• 递归搜索子状态，层次为 dep-1,体积为 sumv+iii,面积为 sum+2ii，半径为 i-1，高度为 j-1。

六 代码

package com.platform.modules.alg.alglib.poj1190;

public class Poj1190 {
    private final int N = 30;
    private final int inf = 0x3f3f3f3f;
    private int n;
    private int m;
    private int minv[] = new int[N];
    private int mins[] = new int[N];
    private int best;

    public String output = "";

    void init() {
        minv[0] = mins[0] = 0;
        for (int i = 1; i < 22; i++) {
            minv[i] = minv[i - 1] + i * i * i;
            mins[i] = mins[i - 1] + 2 * i * i;
        }
    }

    void dfs(int dep, int sumv, int sums, int r, int h) {
        if (dep == 0) {
            if (sumv == n && sums < best) best = sums;
            return;
        }
        if (sumv + minv[dep] > n || sums + mins[dep] > best || sums + 2 * (n - sumv) / r > best) return;
        for (int i = r; i >= dep; i--) {
            if (dep == m) sums = i * i;
            int maxh = Math.min((n - sumv - minv[dep - 1]) / (i * i), h);
            for (int j = maxh; j >= dep; j--)
                dfs(dep - 1, sumv + i * i * j, sums + 2 * i * j, i - 1, j - 1);
        }
    }

    public String cal(String input) {
        init();
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);

        best = inf;
        dfs(m, 0, 0, n, n);
        if (best == inf) {
            output = "0";
        } else {
            output = String.valueOf(best);
        }

        return output;
    }
}

七 测试