首页 > 专题系列 > Java解POJ > POJ 1190 生日蛋糕 [解题报告] Java
2013
11-09

POJ 1190 生日蛋糕 [解题报告] Java

生日蛋糕

问题描述 :

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

温馨提示:

圆柱公式

体积V = πR2H

侧面积A’ = 2πRH

底面积A = πR2

解题代码:

/* @author: */
import java.util.Scanner;
public class Main {
static int end,min;   
static int M,S;
static int dfs(int v,int m,int lastr,int lasth)   
{   
    if(m==0)   
    {   
        //当层数为0时若剩余体积不为0,说明此次搜索不成功,应返回   
        if(v>0||v< 0)   
            return 0;   
        else  
        {   
            //为0,则题目必有解,判断当前外表面积是否比已经得到的最小面积小,若小则置换.   
            end=1;   
            if(min< S)   
                S=min;   
            return 0;   
        }   
    }   
    int i,t=0,j,k,temp;   
    //计算m层最小的体积   
    for(i=1;i<=m;i++)   
        t+=i*i*i;   
    //若当前体积比最小体积还小,返回   
    if(v< t)   
        return 0;   
    t-=m*m*m;   
    int maxr,maxh;   
    //计算当前最底层所能够达到的最大半径.   
    maxr=(int)Math.sqrt((v-t)*1.0/m)< lastr?(int)Math.sqrt((v-t)*1.0/m):lastr;   
    for(i=maxr;i>=m;i--)   
    {   
        //计算确定半径的情况下能够达到的最大高度   
        maxh=(v-t)/(i*i)< lasth?(v-t)/(i*i):lasth;   
        //搜索   
        for(j=maxh;j>=m;j--)   
        {   
            temp=0;   
            //根据当前最底层确定m层蛋糕能达到的最大体积.   
            for(k=0;k<=m-1;k++)   
                temp+=(i-k)*(i-k)*(j-k);   
            //比最大体积还大,肯定会有剩余,返回   
            if(v>temp)   
                break;   
            int tempv=v-i*i*j;   
            //第一层时要加上上表面的面积   
            if(m==M)   
            {   
                if(i*i< S)   
                min=i*i;   
                else  
                {   
                    tempv=v;   
                    continue;   
                }   
            }   
            //加上侧面积,对每一层都适用   
            min+=2*i*j;   
            //若当前得到的面积已经大于已知的最小外表面积,下面的就不用再搜索了,直接返回   
            if(min>S)   
            {   
                tempv=v;   
                min-=2*i*j;   
                continue;   
            }   
            dfs(tempv,m-1,i-1,j-1);   
            //回溯后要恢复数据   
            min-=2*i*j;   
        }   
    }   
    return 0;   
}   

public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
 ///经典搜索,还可以继续剪枝优化   
//S表示最小面积   
int N;   
//end初始为0,有解则变为1.min用来表示每次成功搜索时蛋糕的外表面积   
//v表示当前剩余的体积,m表示剩余蛋糕的层数,lastr表示已经确定的上一层蛋糕的半径,lasth同理   
    
    while(sc.hasNext())   
    {  
       N=sc.nextInt();
       M=sc.nextInt();
 
        int t=0;   
        end=0;   
        S=100000;   
        dfs(N,M,1000,1000);   
        if(end==0)   
            S=0;   
        System.out.printf("%d\n",S);   
    }   
   }
}

  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧