题目链接

圆柱体体积公式：$V = \pi R ^ 2 H$
圆柱体侧面积：$A’ = 2\pi R H$
圆柱体底面积：$A = \pi R ^ 2$

搜索

$\quad$ 搜索框架：从上往下搜索，枚举每层的半径和高度作为分支。
$\quad$ 搜索面对的状态有：正在搜索蛋糕的第 $dep$ 层，当前外表面面积是 $s$，当前体积 $v$，第 $dep + 1$ 层的高度和半径。不妨用数组 $h$ 和 $r$ 分别记录每层的的高度和半径。
$\quad$ 整个蛋糕的“上表面”面积之和等于最底层的圆面积，可以在第 $M$ 层直接累加到中，这样在第 $M - 1$ 层往上搜索中，只需要计算侧面积。

剪枝：

1.上下界剪枝：
计算第$dep$层时：
先枚举$R\in[dep, min(\lfloor \sqrt{N - v} \rfloor, r_{dep + 1} - 1)]$
再枚举$H\in[dep, min(\lfloor (N - v) / R ^ 2 \rfloor , h_{dep + 1} - 1)]$

推导过程：
要满足 $v + \pi R ^ 2 H \le \pi N $
$v + \pi R ^ 2 H \le \pi N $
$\pi R ^ 2 H \le \pi (N - v)$
$R ^ 2 H \le N - v$
$\sqrt{R ^ 2 H} \le \sqrt{N - v}$
$R \sqrt{H} \le \sqrt{N - v}$
$R \le \lfloor \sqrt{N - v} \rfloor$
$R ^ 2 H \le N - v$
$H \le N - v / R ^ 2$

2.优化搜索顺序
在上面确定的范围中，使用倒序枚举。

3.可行性剪枝
可以预处理出从上往下前 $i(1 \le i \le M)$ 层的最小侧面积。显然，当第 $1 \sim i$ 层的半径分别取 $1, 2, 3, \cdots , i$ ，高度也分别取 $1, 2, 3, \cdots , i$ 时，有最小体积与侧面积。
如果当前体积 $v$ 加上 $1 \sim dep - 1$ 层的最小体积大于 $N$ ，可以剪枝。

4.最优性剪枝一
如果当前表面积 $s$ 加上 $a \sim dep - 1$ 层的最小侧面积大于已经搜到的答案，剪枝。

5.最优性剪枝二
利用 $h$ 与 $r$ 数组，$1 \sim dep - 1$ 层体积表示为：$n - v = \sum _{k = 1} ^ {dep - 1} h_k * r_k ^ 2$

$\qquad\qquad\quad $表面积为：$2\sum _{k = 1} ^ {dep - 1} h_k * r_k$

因为$2\sum _{k = 1} ^ {dep - 1} h_k * r_k$

$ = \frac{2}{r_dep} \sum _{k = 1} ^ {dep - 1} h_k * r_k * r_dep$

$\ge \frac{2}{r_dep} \sum _{k = 1} ^ {dep - 1} h_k * r_k ^ 2$

$\ge \frac{2(n - v)}{r_dep}$

所以当 $\frac{2(n - v)}{r_dep} + s$ 大于已经搜到的答案时，可以剪枝。

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 25, INF = 1e9;
int n, m, minv[N], mins[N], R[N], H[N], ans = INF;
void dfs(int u, int v, int s)
{
    if (v + minv[u] > n) return;                        // 剪枝3
    if (s + mins[u] >= ans) return;                     // 剪枝3
    if (s + 2 * (n - v) / R[u + 1] >= ans) return;      // 剪枝5
    if (!u) 
    {
        if (v == n) ans = s;
        return;
    }
    for (int r = min(int(sqrt(n - v)), R[u + 1] - 1); r >= u; r--)       // 剪枝 1 2
        for (int h = min((n - v) / (r * r), H[u + 1] - 1); h >= u; h--)  // 剪枝 1 2
        {
            int t = 0;
            if (u == m) t = r * r;
            R[u] = r, H[u] = h;
            dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
        }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ )               // 剪枝 3  预处理
        minv[i] = minv[i - 1] + i * i * i,
        mins[i] = mins[i - 1] + 2 * i * i;
    R[m + 1] = H[m + 1] = INF;
    dfs(m, 0, 0);
    if (ans == INF) ans = 0;
    cout << ans << endl;
    return 0;
}