A problem description

Make a birthday cake of volume Nπ with M layers, each layer being a cylinder. Suppose the i-th layer of cake from bottom to top is a cylinder with radius Ri and height Hi. When I < m, RI > RI + 1 and hi > hi + 1. Since the cake maker needs to spread the cream, in order to save money as much as possible, it is expected that the outer surface area Q of the cake is the smallest Let Q = Sπ, for the given N and M, find out the cake making plan to minimize S. Except for Q, all of the above data are positive integers.

Two input and output

1 input

2 outputs

Three input and output samples

1 Input sample

100

2

2 Sample output

68

Four Analysis

In this problem, under the condition of a certain volume and number of layers, find the appropriate radius and height to minimize the surface area of ​​the cake. The solution can be searched using the backtracking method.

Five algorithm design

1 Preprocessing

The smallest possible values ​​for the smallest volume and area are calculated from the top layer down. The radius and height of the i-th layer are both i when the minimum volume minv[i] from the top layer (i.e. layer 1) to the i-th layer holds. At this time, only the side area is calculated, and the upper surface area is only calculated once on the bottom layer, and the bottom area of ​​the bottom layer is the total upper surface area.

2 Algorithm design

dep refers to the current depth; sumv and sums refer to the current volume sum and area sum respectively; r and h refer to the current layer radius and height respectively.

a Search upwards from the bottom m layer, when dep =0, the search is completed, and the minimum area is updated.

b Pruning skills

• Exit if the current volume plus the minimum volume of the remaining upper layers is greater than the total volume n.
• If the current area plus the minimum area of ​​the remaining layers above is greater than the minimum area, exit.
• If the current area plus the remaining upper remaining area (remaining volume conversion) is greater than the minimum area, exit.

c Enumerate the radius i, enumerate each possible value i of the cake radius of the dep layer in descending order, the minimum radius of the dep layer is dep

• If dep=m, sums=i * i, the base area is used as the initial value of the outer surface area.
• Calculate the maximum height maxh, which is the upper limit of the cake height of the dep layer, (n-sumv-minv[dep-1]) represents the maximum volume of the dep layer.
• Enumerate the height j, enumerate each possible value j of the height of the dep layer in descending order, and the minimum height of the dep layer is dep.
• Recursively search for substates, the level is dep-1, the volume is sumv+i*i*i, the area is sum+2*i*i, the radius is i-1, and the height is j-1.

Six code

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;
    }
}

Seven test