pku1190 生日蛋糕

#include<stdio.h>
#include<math.h>

const int INF=100000000;
int minS[21],minV[21],ans,n,m;

void dfs(int depth,int r,int h,int leaveV,int sumS)    //参数依次表示当前正访问depth层，该层最大半径和高度是r,h，剩余未用空间leaveV，已用空间的面积

{
    if(depth==0)
    {
        if(leaveV==0&&sumS<ans) ans=sumS;
        return;
    }
    if(sumS+minS[depth]>ans||leaveV<minV[depth]) return;

    for(int i=r-1;i>=depth;i--)
    {
        int startH=(leaveV-minV[depth-1])*1.0/i/i;
        if(startH>h-1) startH=h-1;
        for(int j=startH;j>=depth;j--)
        {
            if(minS[depth-1]+sumS+2*i*j>=ans) continue;
            if(depth==m) dfs(depth-1,i,j,leaveV-i*i*j,sumS+2*i*j+i*i);
            else dfs(depth-1,i,j,leaveV-i*i*j,sumS+2*i*j);        
        }
    }
}

int main()
{
    minV[0]=0;
    minS[0]=0;
    for(int i=1;i<=20;i++)        //整个模型的下界情形是是第一层高度和半径为1，第二层高度和半径为2，依次类推

    {
        minV[i]=minV[i-1]+i*i*i;
        minS[i]=minS[i-1]+2*i*i;
    }
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int maxR=(int)sqrt((n-minV[m-1])*1.0/m)+1;    //最后一层半径的上界

        int maxH=(n-minV[m-1])*1.0/m/m+1;    //最后一层高度的上界

        ans=INF;
        dfs(m,maxR,maxH,n,0);    //从最后一层开始自下而上搜索

        if(ans==INF) printf("0\n");
        else printf("%d\n",ans);
    }
    return 0;
}

总结：

个人总结，剪枝分静态剪枝和冬天剪枝。静态剪枝就是在搜索之前确定解的范围，即解的上界和下界，动态剪枝就是在搜索的过程中，先前通过搜索已假定的解会进一步缩小后面待定的解的范围，此外后面的搜索是基于当前搜索的，若当前搜索的解已明确不是最优解则没有必要进行后续搜索，可直接回溯，另外准确地将题目的一些特殊要求转化成搜索限制也是相当重要的。就本题而言，类似m个数通过搜索取n个数的组合的算法。