题解

从蛋糕从下往上搜索，上表面积就是最下面圆的面积，求解过程注重侧面积和体积即可，

假设当前状态有 $s,v,r_{dep+1\sim m},h_{dep+1\sim m}$， $dep$ 对应的状态，有：

$$n-v\geq r_{dep}^2h_{dep}$$

有上界：

$$r_{dep}=min(n-v,r_{dep+1}-1)$$

$$h_{dep}=min(\frac{n-v}{r_{dep}^2},h_{dep+1}-1)$$

有下界：

$$r_{dep}=dep,h_{dep}=dep$$

很明显，$r_i=i,h_i=i$ 是最小的情况，

它们对应的 $mins_i=2r_ih_i=2i^2,minv_i=r_i^2h_i=i^3$

如果当前结果加最小情况超过答案，那么后面就不会有解。

在有解的情况下，有下面不等式成立：

$$s_{1\sim {dep-1}}=2\sum_{i=1}^{dep-1} r_ih_i,v_{1\sim {dep-1}}=n-v=\sum_{i=1}^{dep-1}r_i^2h_i$$

$$r_i < r_{dep},1\leq i\leq {dep-1}$$

$$s_{1\sim {dep-1}}=2\sum_{i=1}^{dep-1}r_ih_i=\frac{2}{r_{dep}}\sum_{i=1}^{dep-1}r_ih_ir_{dep}\geq\frac{2}{r_{dep}}\sum_{i=1}^{dep-1}r_i^2h_i$$

$$s_{1\sim {dep-1}}\geq\frac{2(n-v)}{r_{dep}}$$

即，$\frac{2(n-v)}{r_{dep}}$ 是后面未求面积的下限，如果 $\frac{2(n-v)}{r_{dep}}+s$ 大于答案，那么这样的状态是不会更优的。

# include <iostream>
# include <cmath>
using namespace std;
const int MAXN = 20 + 5, INF = 1E9;
int n, m, min_s[MAXN], min_v[MAXN], ans = INF, r[MAXN], h[MAXN];
void DFS(int dep, int s, int v)
{
    if(dep == 0)
    {
        if(v == n) ans = min(ans, s);
        return;
    }
    r[dep] = min((int)(double)sqrt(n - v), r[dep + 1] - 1);
    while(dep <= r[dep])
    {
        h[dep] = min((int)(double)(n - v) / (r[dep] * r[dep]), h[dep + 1] - 1) + 1;
        while(dep < h[dep])
        {
            h[dep]--;
            if(ans < s + min_s[dep] || n < v + min_v[dep]) continue;
            if(ans < s + (double)2 * (n - v) / r[dep]) continue;
            if(dep == m) s = r[dep] * r[dep];
            DFS(dep - 1, s + 2 * r[dep] * h[dep], v + r[dep] * r[dep] * h[dep]);
            if(dep == m) s = 0;
        }
        r[dep]--;
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        min_s[i] = min_s[i - 1] + 2 * i * i;
        min_v[i] = min_v[i - 1] + i * i * i;
    }
    r[m + 1] = h[m + 1] = INF;
    DFS(m, 0, 0);
    if(ans == INF) cout << 0 << endl;
    else cout << ans << endl;
    return 0;
}