168. 生日蛋糕（dfs）

我不是女神ヾ 2021-11-09 09:36 374阅读 0赞

题目链接：[https://www.acwing.com/problem/content/170/][https_www.acwing.com_problem_content_170]

7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ

的M层生日蛋糕，每层都是一个圆柱体。

设从下往上数第i层蛋糕是半径为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）。  
数据范围

1≤N≤10000  
,  
1≤M≤20

输入样例：

100  
2

输出样例：

分析：  
暴力大法好。  
dfs搜索，枚举每一层可能的r和h。很明显太过暴力，必然需要剪枝。  
1，每一层的r和h都是有一个确定的范围的。在此范围内枚举即可。  
dep <= r <= min(r\[dep + 1\] -1,sqrt(N-V) )  
dep <= h <= min(h\[dep + 1\] - 1，（N - V) / (r\[dep\] \* r\[dep\]) )  
2，我们可以预处理一下自上往下前i层的最小体积和侧面积。  
如果当前体积 + 最小体积 > N 则必然不行  
如果当前面积 + 最小面积 > Min\_S 则必然不行  
3，通过上面两个剪枝，会少很多次搜索了。但是还远远不够。我们需要通过r和h的关系来进一步剪枝。也就是说，我们可以利用当前的V值，来继续估算一下前dep-1层表面积的大小，从而也可以进行剪枝。  
在有解的情况下，有下面不等式成立：

s1∼dep−1=2∑i=1dep−1rihi,v1∼dep−1=n−v=∑i=1dep−1r2ihi
    
     ri<rdep,1≤i≤dep−1
    
    s1∼dep−1=2∑i=1dep−1rihi=2rdep∑i=1dep−1rihirdep≥2rdep∑i=1dep−1r2ihi
    
    s1∼dep−1≥2(n−v)rdep
    
    即，2(n−v)rdep
    是后面未求面积的下限，如果 2(n−v)rdep+s 大于答案，那么这样的状态是不会更优的。

code

#include"stdio.h"
    #include"string.h"
    #include"math.h"
    #include"algorithm"
    using namespace std;
    #define pi 1
    #define INF 1001010
    
    int N,M;
    int min_s[21],min_v[21];
    int r[21],h[21];
    int m;
    int Min_S,S,V;
    
    void dfs(int dep,int S,int V)
    {
        if(dep == 0)
           {
               if(V == N)
                  Min_S = min(Min_S,S);
               return ;
           }
        r[dep] = min((int)(double)(sqrt(N - V)),r[dep + 1] -1);
        while(r[dep] >= dep)
        {
            h[dep] = min((int)((double)(N - V) / (r[dep] * r[dep])),h[dep + 1] - 1);
            while(h[dep] >= dep)
            {
                if(S + min_s[dep] > Min_S || V + min_v[dep] > N)
                {
                    h[dep] --;
                    continue;
                }
                if(((double)2 * (N - V) / r[dep]) + S > Min_S)
                {
                    h[dep] --;
                    continue;
                }
                if(dep == M)
                    S = r[dep] * r[dep];
                dfs(dep - 1,S + 2 * r[dep] * h[dep],V + r[dep] * r[dep] * h[dep]);
                if(dep == M)
                    S = 0;
                h[dep] --;
            }
            r[dep] --;
        }
    }
    int main()
    {
        for(int i = 1; i <= 20; i ++)
        {
            min_s[i] = i * i * 2 + min_s[i - 1];
            min_v[i] = i * i * i + min_v[i - 1];
        }
        Min_S = 10001010;
        scanf("%d%d",&N,&M);
        m = M;
        h[M + 1] = INF; r[M + 1] = INF;
    
        dfs(M,0,0);
    
        if(Min_S == 10001010)
            printf("0\n");
        else
        printf("%d\n",Min_S);
        return 0;
    }

[https_www.acwing.com_problem_content_170]: https://www.acwing.com/problem/content/170/