题解 P1731 【生日蛋糕】

远航之曲 · 2016-06-23 12:31:42 · 题解

搜索题

朴素的会炸

所以,剪枝是必要的:

最优化剪枝

k层蛋糕的最小表面积可知(h,r都为整数)

当前s可知

那么,s+剩下层数最小表面积>=min最无需再往下搜了

可行性剪枝

k层蛋糕的最小体积minv可知

k层蛋糕的最大体积maxv可知

那么,剩下的体积v不在minv至maxv的范围内,即可停止搜索

include<cstdio>

include<cmath>

include<cstring>

using namespace std；

int ans=999999;
int n,m,temp;
int min[50];
inline int max(int r,int h,int k)
{
    int i,p=0;
    for (i=1;i<=k;i++) p+=(r-i)*(r-i)*(h-i);
    return p;
}
void dfs(int v,int k,int r,int h,int s)
{
    int ss=s,sss=s,vv=v;
    for (int i=r-1;i>0;i--)
    {
        if (k==1) ss=s+i*i;
        for (int j=1;j<h && i*i*j<=v;j++)
        {
            sss=ss+2*i*j;
            vv=v-i*i*j;
            if (vv<min[m-k]) break;
            if (vv>max(i,j,m-k)) continue;
            double tmp;
            tmp=3*pow((double)vv,2.0/3.0)-(i-1)*(i-1);
            if (tmp+sss>ans) continue;
            if (k<m) dfs(vv,k+1,i,j,sss);
                else if (sss<ans) ans=sss;
        }
    }
}
int main()
{
    //freopen("cake.in","r",stdin);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) min[i]=min[i-1]+i*i*i;
    temp=sqrt((double)n)-m*(m-1)/2+1;
    dfs(n,1,temp,temp,0);
    printf("%d\n",ans);
    return 0;
}