# 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

The input contains two lines, the first line is N, which means that the embodiment of making a cake is N π; the second row is M, which represents the number of layers of the cake.

### 2 outputs

Output a positive integer S on a single line (if there is no solution, then S = 0)

100

2

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 = mins = 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);
m = Integer.parseInt(line);

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

return output;
}
}```

# Seven test Posted by El_Dudereno on Thu, 08 Sep 2022 21:08:15 +0300