生日蛋糕(深搜剪枝,讲解通俗易懂,还有个人手写笔记)

                                                    生日蛋糕

解题思路:

       有的时候,将题读懂,问题就解决一半了。

       题中给出体积和层数,要求合理安排每一层的半径Ri、高度Hi,使得蛋糕的外表面积最小(最下层的底面除外),要求有:Hi > Hi+1且Ri>Ri+1(也就是说,蛋糕越往上越小)。

       计算的过程中,直接计算侧面积就可以,上表面积的值就是最下底层的圆面积,等到最后直接加到总的值里。

       怎么去合理的搜索R和H成为了解决本题的关键。(不剪枝直接超时)

       设当正在搜索的蛋糕在dep层,当前外表面面积s,当前体积v,h1和r1分别记录每层的高度和半径。

剪枝:(切记,R和H都是整数)

(1)上下界剪枝

         R与H的范围

        

       分析左端:

       

       分析右端:

      

(2)优化搜索顺序

       根据确定的范围,使用倒序枚举。

(3)预处理最小体积和侧面积,意思就是当你搜完第三层的时候,你根据预处理得出的第二层加第一层的体积和表面积,加上第三层搜索到的值进行判断,如果不符合,直接递归返回。

(4)最优剪枝(涉及数学推导)

     

    

    

(字丑莫怪。。。)

例题地址:https://loj.ac/problem/10019

AC代码: 

#include<bits/stdc++.h>

using namespace std;

const int inf = 1e9;
int n,m,sum = 99999999;
int h1[30],r1[30];
int minv[30],mins[30];
void dfs(int s,int v,int dep)//当前表面积,体积,层数
{
    if(v+minv[dep]>n)//此时的体积加上还没有计算部分的预估最小体积
        return;//直接将此时的体积与总体积做比较,也是可以AC
    if(s+mins[dep]>=sum)//此时的面积,加上还没有计算部分的预估最小面积
        return;//直接将此时的面积与总面积做比较,也是可以AC
    if(s + 2*(n-v)/r1[dep+1] >= sum)//非常非常关键的一步优化
        return;//根据当前得出的数据,实际计算剩余
    if(dep == 0)
    {
        if(n == v)//容易被忽略的一步,给定体积必须全用
           sum = s;
        return;
    }
    for(int r = min((int)sqrt(n-v),r1[dep+1]-1);r>=dep;r--)//改变循环过了80%的数据必须规定下界
    {
       for(int h = min((int)(n-v)/(r*r),h1[dep+1]-1);h>=dep;h--){
        h1[dep] = h;
        r1[dep] = r;
        int ss = 0;
        if(dep == 1)//如果到了最后一层,将圆面加上
            ss = r1[m]*r1[m];
        dfs(s+2*r*h+ss,v+r*r*h,dep-1);
       }
    }

}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){//最小体积与面积的预估算,为剪枝做准备
        minv[i] = minv[i-1] + i*i*i;
        mins[i] = mins[i-1] + 2*i*i;
    }
    h1[m+1] = inf;//非常重要的一步
    r1[m+1] = inf;//设定边界
    dfs(0,0,m);
    printf("%d
",sum);
    return 0;
}

总是想快一点完成任务,有一些路会挑一些捷径,到后来发现那不是捷径,那是坑。 

原文地址:https://www.cnblogs.com/codepeanut/p/12920497.html