`
阿尔萨斯
  • 浏览: 4108894 次
社区版块
存档分类
最新评论

POJ 1190 生日蛋糕(DFS:优化剪枝)

 
阅读更多

POJ 1190 生日蛋糕(DFS:优化剪枝)

http://poj.org/problem?id=1190

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外,以上所有数据皆为正整数)

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

分析:

首先我们令最下面一层为第M层,然后最上面一层是第1层.那么我们知道从下到上,每层的圆柱体半径R和H都是整数且都递减.

初始我们给出体积为V,层数为M,所以我们知道第M层的半径R>=M且H>=M,所以我们可以通过第M层圆柱的体积R^2*H_max=Vm<V 得出第M层高H的最大值H_max<V/(R*R)+1 ,同理可以退出R_max<srqt(V/M)+1.

到这里我们有了H和R的上界了.我们在求出sumv[i]表示从第一层到第i层的体积和最小值.以及sums[i]表示从第一层到第i层的侧面积和最小值.

下面就是dfs了,我们令dfs(int floor,int preR,int preH,int leftV,intS)表示当前在第floor层,前一层floor+1时我们取了半径为preR,高为preH.到了floor层我们还剩下leftV体积未分配,且我们已经产生了S的面积.

dfs的终态是:floor=0且leftV正好==0时,如果S的值< ans ,那么我们就用S去更新ans.

当然dfs中还需要剪枝了.

第一个剪枝是:

if((preR>1)&& 2 * vLeft/(preR-1)+ s>=ans)

这句话的含义是如果剩下的体积只做成一个圆柱体的话,得到的侧面积是最少的,且如果这样的话最后的总侧面积还是大于ans ,那么我们可以不用求下面的dfs,无用功.

第二个剪枝就是:

if(vLeft-sumV[floor]<0||s+sumS[floor]>=ans)

剩余的体积不足,或者面积已经超了.

AC代码:

#include<cstdio>
#include<cmath>
using namespace std;
int V,M;
int ans=65535;
int sumV[21],sumS[21];
void dfs(int floor,int preR,int preH,int leftV,int s)
{
    if(floor==0)
    {
        if(leftV==0&&s<ans) ans=s;
        return ;
    }
    if(preR>1 && 2*(leftV/(preR-1))+s>=ans) return;
    if(leftV<sumV[floor] || s+sumS[floor]>=ans) return;
    for(int r=preR-1;r>=floor;r--)
    {
        if(floor==M) s=r*r;
        int H_max=(1.0*leftV/(r*r))+1;
        if(H_max>preH-1) H_max=preH-1;
        for(int h=H_max;h>=floor;h--)
            dfs(floor-1,r,h,leftV-r*r*h,s+2*r*h);
    }
}
int main()
{
    scanf("%d%d",&V,&M);
    sumV[0]=sumS[0]=0;
    for(int i=1;i<=20;i++)//最多20层
    {
        sumV[i]=sumV[i-1]+i*i*i;
        sumS[i]=sumS[i-1]+2*i*i;
    }
    int R_max=sqrt(1.0*V/M)+1;
    int H_max=(1.0*V/(M*M))+1;
    dfs(M,R_max,H_max,V,0);
    if(ans==65535) ans=0;
    printf("%d\n",ans);
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics