一.题目链接：

生日礼物

二.题目大意：

目标为做一个体积为 πn 层数为 m 的蛋糕.

并使得蛋糕从上到下，半径与高度均递增.

现往蛋糕上抹奶油（覆盖蛋糕表面，最底层的底面除外）

为了使花费最小，找出一种制作蛋糕的方法，使得奶油的覆盖面积最小.

输出奶油的最小覆盖面积 / π.

三.分析：

将蛋糕的层数从上到下编号为 1,2 ... m，记答案为 ans.

搜索时所需的状态有 当前的层数 i，当前的侧面积 s，当前的体积 πv.

易得：蛋糕的侧面积 == 蛋糕各层圆柱的侧面积 + 最底层圆柱的底面积.

由于层之间的半径与高度有约束条件，不妨记录各层的半径与高度.

① 上下界剪枝：

由于并使得蛋糕从上到下，半径与高度均递增

所以第 i 层蛋糕的半径与高度的下界均为 i，上界分别为

现从体积限制来分析上界，假设已选的蛋糕体积为 πv，第 i 层蛋糕的体积为

则

即：

综上所得：

② 优化搜索顺序：

倒序枚举，从下往上枚举.

这是因为底层蛋糕的体积大，先选体积大的，可以减少分支.

③ 可行性剪枝：

可以预先处理出，从上到下的最小体积前缀和 与 最小侧面积前缀和.

显然，当半径依次取 1,2 ... m ；高度依次取 1,2 ... m 时，两者取得最小值.

如果 ，则可剪枝.

④ 最优性剪枝一：

如果 ，则可剪枝.

⑤最优性剪枝二：（这里没想到啊。。）

利用体积与表面积的关系使用放缩法.

1 ~ i - 1 层的体积可表示为

1 ~ i - 1 层的侧面积可表示为

当 时，则可剪枝.

详见代码.

四.代码实现： 

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define lc k * 2
#define rc k * 2 + 1
#define pi acos(-1.0)
#define ll long long
#define ull unsigned long long
using namespace std;

const int M = (int)1e2;
const int mod = 99991;
const int inf = 0x3f3f3f3f;

int n, m;
int ans = inf;
int r[25], h[25];
int min_v_sum[25];
int min_s_sum[25];

/**
r1 h1 r2 h2
2  1  4  6
**/

void dfs(int deep, int s, int v)
{
    if(!deep)
    {
        if(v == n)
            ans = min(ans, s);
        return;
    }
    r[deep] = min((int)sqrt(n - v), r[deep + 1] - 1);
    while(r[deep] >= deep)
    {
        h[deep] = min((int)(double)(n - v) / r[deep] / r[deep], h[deep + 1] - 1) + 1;
        while(h[deep] > deep)
        {
            --h[deep];
            if(v + min_v_sum[deep] > n)             continue;
            if(s + min_s_sum[deep] > ans)           continue;
            if(s + 2.0 * (n - v) / r[deep] > ans)   continue;
            if(deep == m)   s = r[deep] * r[deep];
            dfs(deep - 1, s + 2 * r[deep] * h[deep], v + r[deep] * r[deep] * h[deep]);
            if(deep == m)   s = 0;
        }
        --r[deep];
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; ++i)
    {
        min_s_sum[i] = min_s_sum[i - 1] + 2 * i * i;
        min_v_sum[i] = min_v_sum[i - 1] + i * i * i;
    }
    h[m + 1] = r[m + 1] = inf;
    dfs(m, 0, 0);
    if(ans == inf)  ans = 0;
    printf("%d\n", ans);
    return 0;
}