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