POJ-1190 生日蛋糕(dfs+剪枝)

生日蛋糕

题目链接http://poj.org/problem?id=1190

Time Limit: 1000MS Memory Limit: 10000K

Description

7月17日是Mr.W的生日,ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕,每层都是一个圆柱体。
设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时,要求 R i &gt; R i + 1 且 H i &gt; H i + 1 。 Ri &gt; Ri+1且Hi &gt; Hi+1。 Ri>Ri+1且Hi>Hi+1。
由于要在蛋糕上抹奶油,为尽可能节约经费,我们希望蛋糕外表面(最下一层的下底面除外)的面积Q最小。
令Q = Sπ
请编程对给出的N和M,找出蛋糕的制作方案(适当的Ri和Hi的值),使S最小。
(除Q外,以上所有数据皆为正整数)

Input

有两行,第一行为N(N <= 10000),表示待制作的蛋糕的体积为Nπ;第二行为M(M <= 20),表示蛋糕的层数为M。

Output

仅一行,是一个正整数S(若无解则S = 0)。

Sample Input
100
2

Sample Output
68

Hint

圆柱公式
体积V = πR2H
侧面积A’ = 2πRH
底面积A = πR2


这题未知量比较多,所以搜索的变量也会多几个,我们可以对层数、半径和高度进行搜索,只要这三者确定了,那么一切都好说。所以说这题的想法并不会很难,但关键在于它的剪枝比较多而已。。。

#include<cstdio>
#include<cmath>
int ans=99999999,n,m,vh[10010],vr[10010],minn[40];
void dfs(int c,int v,int s,int r,int h);
int main()
{
    scanf ("%d%d",&n,&m);
    int t=m;
    for (int i=1; i<=m; i++)
     minn[t--]=i*i*i;                   //每一层的最小体积 
    dfs(0,0,0,sqrt(n),n);
    printf ("%d\n",ans);
    return 0;
}
void dfs(int c,int v,int s,int r,int h)     //对层数、体积、表面积、半径、高度搜索
{
    if (c==m && v==n)
    { ans=(ans>s)?s:ans;
      return;
    }
    if (v+minn[c+1]>n) return;            
    if (s+(n-v)/r>ans) return;                 //每层最小表面积 
    else if (c>=m || v>=n) return;
    for (int i=r; i>=m-c; i--)   //枚举半径
     if (!vr[i])
      for (int j=h; j>=m-c; j--)    //枚举高度
       if (!vh[j])
       { if (v+i*i*j>n) continue;
         if (c!=0)
         { if (s+2*i*j>ans) return;
           vr[i]=1,vh[j]=1;
           dfs(c+1,v+i*i*j,s+2*i*j,i,j);
           vr[i]=0,vh[j]=0;
         }
         else                      //第0层的表面积特判
         { if (s+2*i*j+i*i>ans) return;
           vr[i]=1,vh[j]=1;
           dfs(c+1,v+i*i*j,s+2*i*j+i*i,i,j);
           vr[i]=0,vh[j]=0;
         }
       }
}

POJ-1190 生日蛋糕(dfs+剪枝)
79ms,还好。。。

上一篇:POJ 1699


下一篇:POJ-1321棋盘问题(dfs深搜)