分析

• 分析题目可知下层的蛋糕直径一定严格大于上层蛋糕的直径。与题目不同，这里假设最上面一层蛋糕为第1层蛋糕，最底部的蛋糕为第m层蛋糕。

• 我们一次枚举每层蛋糕即可。

• 蛋糕的总表面积为：$R_m^2+(2R_mh+…2R_1h)$。忽略$\pi$。

• 考虑如何剪枝：

（1）优化搜索顺序：我们应该从最底层蛋糕向最上层蛋糕搜索（从第m层向第1层搜索），这样搜索空间比较小。另外因为R是平方级别的，我们应该先枚举R，再枚举h，并且按照从大到小的顺序枚举R、h，这样留给之后的决策就会更少，搜索空间会减小。

（2）排除等效冗余：无

（3）可行性剪枝：

​ （3.1）假设当前考察的是第u层，因为其上面还有u-1层且下层比上层半径大，所以$u<=R(u)<=R(u+1)-1$，另外假设第u层以下的体积是V，则$n-V>=R(u)^2h$，所以$R(u)<=\sqrt{(n-V)/h}<=\sqrt{n-V}$，所以$u<=R(u)<=min(R(u+1)-1,\sqrt{n-V})$。

​ （3.2）同理：$u<=H(u)<=min(H(u+1)-1,(n-V)/R^2)$。

​ （3.3）从上到下前u层的体积最小值minv[u]，以及前u层的表面积最小值mins[u]。假设第u层以下的体积是V，表面积是S（已经包含了$R_m^2$），我们必须保证$minv[u]+V<=n$，$mins[u]+S<ans$（ans是我们当前记录的最小表面积）。

​ （3.4）考虑从上到下前u层的面积和体积之间的关系（假设第u层以下的体积是V，表面积是S（已经包含了$R_m^2$））：
$$ S_{1u} = \sum_{k=1}^{u}2R_kh_k \\ n-V= \sum_{k=1}^{u}R_k^2h_k $$

$$ S_{1u} = \sum_{k=1}^{u}2R_kh_k = \frac{2}{R_{u+1}}\sum_{k=1}^{u}R_kh_kR_{u+1} > \frac{2}{R_{u+1}}\sum_{k=1}^{u}R_k^2h_k \\ $$

所以有：
$$ S_{1u} > \frac{2(n-V)}{R_{u+1}} $$
考虑极端情况，当V取到n的时候，$S_{1u}=0$，可以取到等号，因此：
$$ S_{1u} \ge \frac{2(n-V)}{R_{u+1}} $$
所以有
$$ S + S_{1u} \ge S + \frac{2(n-V)}{R_{u+1}} $$
如果：
$$ S + S_{1u} \ge S + \frac{2(n-V)}{R_{u+1}} \ge ans $$
的话，可以提前结束（ans是我们当前记录的最小表面积）

（4）最优性剪枝：无。

#include <iostream>
#include <cmath>

using namespace std;

const int N = 25, INF = 1e9;

int n, m;  // 总体积、层数
int minv[N], mins[N];  // 从上到下最小体积和，面积和(只考虑侧面积)
int R[N], H[N];  // R[1],H[1]表示最高层的半径和高度
int ans = INF;

// u: 当前遍历那一层; v:已经使用过的体积; 
// s:占用的表面积(已经包含了Rm^2)
void dfs(int u, int v, int s) {

    // 优化3-3
    if (v + minv[u] > n) return;
    if (s + mins[u] >= ans) return;

    // 优化3-4
    if (s + 2 * (n - v) / R[u + 1] >= ans) return;

    if (!u) {
        if (v == n) ans = s;
        return;
    }

    // 优化1,3-1,3-2
    for (int r = min(R[u + 1] - 1, (int)sqrt(n - v)); r >= u; r--)
        for (int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; h--) {
            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++) {
        minv[i] = minv[i - 1] + i * i * i;
        mins[i] = mins[i - 1] + 2 * i * i;
    }

    R[m + 1] = H[m + 1] = INF;  // 哨兵，因为优化3-1,3-2需要取最小值

    // 优化1
    dfs(m, 0, 0);

    if (ans == INF) ans = 0;
    cout << ans << endl;

    return 0;
}