https://loj.ac/problem/10019

题目描述

??有一个\(M\)层的生日蛋糕，它的体积为\(Nπ\)，它每层的半径随层数增加而增加，我们要在蛋糕外表面(出最后一层底面外)涂抹奶油，求蛋糕上涂抹奶油的面积最小为多少。输出\(Q\)表示涂抹面积为\(Qπ\)。

思路

??\(dfs\)的剪枝主要包括\(5\)类，优化搜索顺序，排除等效冗余，可行性剪枝，最优性剪枝，记忆化。

??这道题我们主要运用前四个剪枝。

??1、上下界剪枝

????当我们递归到第\(dep\)层时，我们只需要从以下范围枚举

????先枚举\(R∈[ dep ， min\{\sqrt{N-v}，r[ dep + 1] - 1\}]\)

????再枚举\(H∈[ dep ， min\{(N-v)/R^2，r[ dep + 1] - 1\}]\)

????这里\(R\)和\(H\)的下界是比较显然的，而上界都可以由公式\(πR^2H = π(N - v)\)得到

??2、优化搜索顺序

????这是这道题最重要的优化，虽然简单，却大大提高了搜索效率。在\(loj\)上测试，正序搜索总时间\(1300ms+\)，倒序搜索总时间\(9ms\)。

????倒序搜索可以快速得到较优解，从而结合其他剪枝避免了次优解的过多更新，但这里的严谨证明根本无从下手，作为\(OIer\)我们可以通过造数据来测试哪一种搜索

??顺序更快。

??3、可行性剪枝

????我们可以预处理出还剩下\(dep\)层的最小体积\(minv[dep]\)，这样就有了以下剪枝：

????\(minv[ dep ] + v>N\) 直接\(return\)

??4、最优性剪枝

????\(①\)与可行性剪枝类似，我们可以预处理出还剩下\(dep\)层的最小表面积\(mins\)，如果\(mins[dep] + s>ans\)，可以\(return\)。

????\(②\)这个剪枝就比较复杂，需要一定的数学推导

????　首先利用\(h\)和\(r\)数组，\(1\sim dep-1\)的体积可表示为：
\[ N-v=\sum_{k=1}^{dep-1} h[k]*r[k]^2 \] 　
??????同时，\(1\sim dep-1\)层的表面积可表示为：
\[ N-v=2\sum_{k=1}^{dep-1} h[k]*r[k] \]
??????而显然我们可以得到
\[ S=2\sum_{k=1}^{dep-1} h[k]*r[k]=\frac{2}{r[dep]}* \sum_{k=1}^{dep-1} (h[k]*r[k]*r[dep]) \]
??????由于对于\(\forall k∈[ 1， dep - 1]，r [ k ]<r [ dep ]\)，所以：
\[ \frac{2}{r[dep]}* \sum_{k=1}^{dep-1} (h[k]*r[k]*r[dep])\ge \frac{2}{r[dep]}* \sum_{k=1}^{dep-1} (h[k]*r[k]^2) \]
???? 而后面的求和公式即为我们上面提到的\(N - v\)，所以联立可得：
\[ S\ge \frac{2(N-v)}{r[dep]} \]
???? 所以当这个值加目前的表面积\(s\)大于\(ans\)时可以剪枝。

???? 这个剪枝的效率也相当高，未加此剪枝时间\(1350ms+\)。

代码

#include <bits/stdc++.h>
using namespace std;
int n,m,ans=0x7fffffff;
int mins[30],minv[30];
bool check1(int d,int s)
{
    if(mins[d]+s>ans)return 1;
    return 0;
}
bool check2(int d,int v)
{
    if(minv[d]+v>n)return 1;
    return 0;
}
void dfs(int dep,int s,int v,int r,int h)
{
    if(dep==0)
    {
        if(v==n&&s<ans)ans=s;
        return ;
    }
    if(check1(dep,s)||check2(dep,v))return ;
    if(2*(n-v)/r+s>ans)return ;
    for(int R=min((int)sqrt(n-v),r-1);R>=dep;R--)
    {
        if(dep==m)s=R*R;
        for(int H=min((int)(n-v)/(R*R),h-1);H>=dep;H--)
//            cout<<H<<' '<<R<<endl;
            dfs(dep-1,s+2*R*H,v+R*R*H,R,H);
    }
}
int main() 
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        mins[i]=mins[i-1]+2*i*i;
        minv[i]=minv[i-1]+i*i*i;
    }
//    for(int i=1;i<=m;i++)
//        printf("%d %d\n",mins[i],minv[i]);
    dfs(m,0,0,n+1,n+1); 
    printf("%d",ans);
    return 0;
}

生日蛋糕

原文：https://www.cnblogs.com/fangbozhen/p/11760579.html