7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。 
设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。 
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。 
令Q = Sπ 
请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。 
（除Q外，以上所有数据皆为正整数） 

有两行，第一行为N（N <= 10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M <= 20)，表示蛋糕的层数为M。

仅一行，是一个正整数S（若无解则S = 0）。

100

2

68

圆柱公式 
体积V = πR²H 
侧面积A' = 2πRH 
底面积A = πR² 

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

const int N=;

const int inf=0x3f3f3f3f;

int mins[N],minv[N];

int ans,n,m;

void init()

{

    int i;

    mins[]=;

    minv[]=;

    for(i=;i<N;i++)//从顶层向下计算出最小的面积和体积值，都提出pi处理

    {

        mins[i]=mins[i-]+*i*i;

        minv[i]=minv[i-]+i*i*i;

    }

}

从m层向上搜索，dep是当前层数，sums，sumv指搜索到现在的面积和体积的值，r，h指当前层的半径和高度

void dfs(int dep,int sums,int sumv,int r,int h)

{

    int maxh,i,j;

    if(dep==)//搜索完成了，dep==0；

    {

        if(sumv==n&&sums<ans)//此时sumv==n，若面积比当前ans小的话，更新ans；

        {

            ans=sums;

        }

        return ;

    }

    if(sums+mins[dep-]>ans||sumv+minv[dep-]>n||*(n-sumv)/r+sums>=ans) return ;
//三个重要的剪枝，当前面积加上上面几层最小的可能面积大于ans;同理，体积;ans-sums>2*(n-sumv)/r;

    for(i=r-;i>=dep;i--)

    {

        if(dep==m)//如果是最底下的那层，先加上他的上面的面积，这样以后就只要考虑侧面的面积就可以了

        {

            sums=i*i;

        }

        maxh=min(h-,(n-sumv-minv[dep-])/(i*i));//去最小值做最大高度h=v/(r*r)

        for(j=maxh;j>=dep;j--)

        {

            dfs(dep-,sums+*i*j,sumv+i*i*j,i,j);//到上一层搜索

        }

    }

}

int main()

{

    init();

    while(~scanf("%d%d",&n,&m))

    {

        ans=inf;

        dfs(m,,,n+,n+);

        if(ans==inf) ans=;

        printf("%d\n",ans);

    }

    return ;

}