Problem 1190 （c++）

首先吐槽一下求面积和体积不用π。
其实不减枝的代码还是很好写的:
//m为蛋糕的层数
//v为当前已涂的体积
//s为当前已涂得到的S
//r和h为当前层的半径和高
void dfs(int m,int v,int s,int r,int h)
{
    //推出条件
    if(m == 0)
    {
        if(ans > s && v == N) ans = s;
        return;
    }
    //枚举可能的解
    for(int i = r-1; i >= m; i--)
    {
        for(int j = maxh; j >= m; j--)
        {
            if(m == M) s = i * i;
            dfs(m-1,v+i*i*j,s+2*i*j,i,j);
        }
    }
}

然后就是减枝呢，四个减枝的条件：
    先打表，算出每层蛋糕的最小体积和表面积(minv[i]和mins[i])，然后在来减枝
    一、v+minv[m-1]  > V
            v为已经涂的体积，那么如果v加上下一层最小的体积比总体积V还大，这显然是不可能的，减去

    二、s+min[m-1] > ans
            s为已经涂的面积，那么s加上下一次最小的面积比当前求得的ans还大，显然不需要dfs了，减去

    三、2*(V-v)/r + s >= ans
           已经涂了s，那么还剩下rest_s = sum{2*Ri*Hi} >= sum(2*Ri*Ri*Hi/Rk} = 2*(V-v)/r （设k为当前层的半径）。如果rest_s加上s大于等于ans，那么也不用在dfs了。

    四、maxh = Min((N-v-minv[m-1])/(i*i),h-1)
           当枚举半径为i时，当前最低的可能高为maxh = Min((N-v-minv[m-1])/(i*i),h-1)。

下面是代码：

#include<stdio.h>
#include<string.h>
#define maxn 22
#define INF 100000000
#define Min(a,b) (a < b ? a : b)
int N;
int M;
int ans;
int minv[maxn],mins[maxn];

void init()
{
    minv[0] = 0;
    mins[0] = 0;
    for(int i = 1; i <= N; i++)
    {
        minv[i] = minv[i-1] + i*i*i;
        mins[i] = mins[i-1] + 2*i*i;
    }
}
//m为蛋糕的层数
//v为当前的体积
//s为当前得到的面积
//r和h为当前层的半径和高
void dfs(int m,int v,int s,int r,int h)
{
    if(m == 0)
    {
        if(ans > s && v == N) ans = s;
        return;
    }
    if(s + mins[m-1] > ans || v + minv[m-1] > N || 2*(N-v)/r + s >= ans) return;
    for(int i = r-1; i >= m; i--)
    {
        int maxh = Min((N-v-minv[m-1])/(i*i),h-1);
        for(int j = maxh; j >= m; j--)
        {
            if(m == M) s = i * i;
            dfs(m-1,v+i*i*j,s+2*i*j,i,j);
        }
    }
}
int main()
{
    scanf("%d%d",&N,&M);
    ans = INF;
    dfs(M,0,0,N+1,N+1);
    if(ans == INF) printf("0\n");
    else printf("%d\n",ans);
    return 0;
}