pku 1190

2009年8月6日 星期四

题目链接：PKU 1190 生日蛋糕 

分类：一道DFS

题目分析与算法原型：
         因为题目给的数据范围不大，蛋糕总共不会超过20层，所以可以采用DFS解决，先从最底层即m层开始往上枚举，每上一层，层数减1，直到最顶层，对于每层，枚举其最大的可能半径到最小的可能半径 ，以及对应的最大的高度到最小的高度，然后DFS。
        注意这题可以做一些减枝，因为题目说每层蛋糕的半径和高度都比下面层的蛋糕的小，就是说，至少小1，那么，可以发现如果当前是第x层，那么该层的蛋糕的高度和半径至少是x（假设最顶层的半径和高度都取最小，为1）然后可以根据当前的累积面积和剩余的体积可以估计出此层开始递归计算出的最小面积和所剩的体积，然后对比从剩余的体积和最小面积，如果不满足一定的约束即return ,这样可以减一些时间的开销.        
 
 1#include<stdio.h>
 2#include<math.h>
 3#define max 0x7fffffff
 4int mins[25],minv[25],n,m,ms;
 5
 6//       当前层数,下面那层的半径,高度,剩余体积,所用的面积
 7void dfs(int cur_f,int last_r,int last_h,int leave_v,int sum_s)//从最底层n开始计算到1层
 8{
 9    int i,j,max_h;
10    if(sum_s+mins[cur_f]>=ms||leave_v<minv[cur_f])return;
11    //估算所用的最小面积比现有的最小面积大,或者所用的体积不满足要求
12    if(cur_f==0)
13    {
14        if(leave_v==0&&ms>sum_s)ms=sum_s;
15        return ;
16    }
17    for(i=last_r-1;i>=cur_f;i--)
18    {
19        int kk=(int)((leave_v-minv[cur_f-1])/(double)(i*i));
20        max_h=kk < (last_h-1)? kk :(last_h -1);
21        for(j=max_h;j>=cur_f;j--)
22        {
23             if(2*(leave_v-i*i*j)/i+sum_s+2*i*j>=ms) continue;
24             //若估算所用的最小面积比现有的最小面积大则忽略该次枚举
25             int v=i*i*j,s=2*i*j;
26             if(cur_f==m)s+=i*i;
27             dfs(cur_f-1,i,j,leave_v-v,sum_s+s);
28        }
29    }
30}
31
32int main()
33{
34    int i;
35    mins[0]=0;
36    minv[0]=0;
37    for(i=1;i<=20;i++)   //mins[i]和minv[i]代表从第一层开始累积到第i层，蛋糕的最小可能面积和体积
38    {
39        mins[i]=mins[i-1]+2*i*i;
40        minv[i]=minv[i-1]+i*i*i;
41    }
42    while(scanf("%d%d",&n,&m)!=EOF)
43    {
44        ms=max;
45        int beg=(int)sqrt((double)n)+1;
46        dfs(m,beg,beg,n,0);
47        if(ms!=max)printf("%d",ms);
48        else printf("0\n");
49    }
50    return 1;
51}
52

posted on 2009-08-07 00:04 蜗牛也Coding 阅读(436) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年7月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜