A Za, A Za, Fighting...

坚信：勤能补拙

PKU 1190 生日蛋糕

问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1190

思路:
DFS+减枝，好题

代码:
 1 /*
 2  * N = R[1]^2*H[1] + R[2]^2*H[2] +  + R[M]^2*H[M]
 3  * S = R[1]^2 + 2R[1]*H[1] + 2R[2]*H[2] +  + 2R[M]H[M]
 4  */
 5 #include<stdio.h>
 6 #include<stdlib.h>
 7 #include<string.h>
 8 #include<math.h>
 9 #define MAX_LEVEL 21
10 #define INF 0x7FFFFFFF
11 /* from top level to the i[th] level, the minimum total volumn and area */
12 int min_volumn[MAX_LEVEL], min_area[MAX_LEVEL];
13 int n, m;
14 int rt;
15 
16 void
17 init()
18 {
19     int i;
20     rt = INF;
21     min_volumn[0] = min_area[0] = 0;
22     for(i=1; i<MAX_LEVEL; i++) {
23         min_volumn[i] = min_volumn[i-1] + i*i*i;
24         min_area[i] = min_area[i-1] + 2*i*i;
25     }
26 }
27 
28 /* from bottom(m[th] level) to the top */
29 void
30 dfs(int level, int last_r, int last_h, int cur_volumn, int cur_area)
31 {
32     int r, h, tmp, v, a;
33     if(cur_volumn+min_volumn[level]>n || cur_area+min_area[level]>=rt)
34         return;
35     /* ADD this pruning according the volumn&area formula */
36     if(2*(n-cur_volumn)/last_r+cur_area >= rt)
37         return;
38     if(level==0) {
39         if(cur_volumn == n)
40             rt = cur_area<rt ? cur_area : rt;
41         return;
42     }
43     /* the minimal r in [level] would be level */
44     for(r=last_r-1; r>=level; r--) {
45         tmp = (int)((n-cur_volumn-min_volumn[level-1])/(double)(r*r));
46         tmp = tmp>(last_h-1) ? (last_h-1) : tmp;
47         for(h=tmp; h>=level; h--) {
48             v = r*r*h;
49             a = 2*r*h;
50             if(level == m)
51                 a += (r*r);
52             dfs(level-1, r, h, cur_volumn+v, cur_area+a);
53         }
54     }
55 }
56 
57 int
58 main(int argc, char **argv)
59 {
60     int max_m_r, max_m_h;
61     while(scanf("%d %d", &n, &m) != EOF) {
62         init();
63         max_m_r = (int)(sqrt((n-min_volumn[m-1])/(double)m)) + 1;
64         max_m_h = (int)((n-min_volumn[m-1])/(double)(m*m)) + 1;
65         dfs(m, max_m_r, max_m_h, 0, 0);
66         if(rt == INF)
67             printf("0\n");
68         else
69             printf("%d\n", rt);
70     }
71 }

posted on 2010-08-03 12:33 simplyzhao 阅读(501) 评论(0)  编辑 收藏 引用 所属分类: B_搜索


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


导航

<2010年8月>
日一二三四五六
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜