本文共 1760 字，大约阅读时间需要 5 分钟。

DFS_生日蛋糕

时间限制: 2 Sec 内存限制: 10 MB 提交: 516 解决: 102 题目描述 7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。 设从下往上数第i(1 <= i <= M)层蛋糕是半径为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）。 样例输入

100

2

样例输出

68

题意：蛋糕从下往上，每一层的半径和高都越来越小，且为整数。已知蛋糕的体积为Nπ，蛋糕的层数为M，输出S，使满足条件的蛋糕外表面（最下一层的下底面除外）的面积Q=Sπ最小。

解题思路：用DFS遍历每一层的蛋糕的高和半径，注意必须剪枝，否则会超时

斜体样式

AC代码：#include 
   
    //万能头文件using namespace std;#define maxn 1000000007   typedef long long ll;int s,n,m,sum;void DFS(int r,int h,int v,int s,int k)//参数分别代表半径，高，剩余体积，当前表面积，当前层数{    if(s+2*v/r>sum) return;  //剪枝：V=r1*r1*h1+r2*r2*h2+...     S=2*r1*h1+2*r2*h2+...    if(k==m)             因为半径越来越小，所以2*v/r是剩余表面积的最小值，若s+2*v/r>当前最小表面积则不用继续递归    {        if(v==0) //层数和体积都满足条件则和最小表面积比较        sum=min(sum,s);        return; //不管体积满不满足，层数到了就不能继续递归    }    for(int R=r-1;R>=m-k;R--) //随着递归半径越来越小，且要保证最上面一层至少为1，从上往下半径越来越大，且    {                           每一层半径都为整数，所以半径至少等于层数。（R>=m-k）        int hk=min(h-1,v/(R*R));     //因为体积要减少R*R*H，所以H不        for(int H=hk;H>=m-k;H--)     能超过v/(R*R)，否则剩余体积为负        {                           int S;            if(k==0)                S=R*R+2*R*H;      //表面积要加上最下面的一个圆面                else                    S=s+2*R*H;            DFS(R,H,v-R*R*H,S,k+1);        }    }}int main(){    while(scanf("%d%d",&n,&m)==2)    {        sum=maxn; //最小表面积先赋初值        DFS(sqrt(n)+1,n+1,n,0,0);  //因为v=r*r*h,所以半径最大为根号n,同理高最大为n,为避免出现不可知的错误，所以        if(sum==maxn)                多加一个1....            printf("0\n");          //一定要注意不要用cout<<,这题对时间要求很高，cout<
   

注：第一次发博客，还不太会，可能排版不好看…

而且还只是ACM入门小白，如果发现有问题请多多指教！_(￣▽￣)*

转载地址：https://blog.csdn.net/qq_44632981/article/details/97541216 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！