亚洲伊人久久大香线蕉苏妲己,91亚洲国产成人久久精品,亚洲国产精品人久久

堅信：勤能補拙

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 閱讀(514) 評論(0) 編輯收藏引用所屬分類: B_搜索

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: PKU 3400 Dropping the stones PKU 2312 Battle City (Cont.) PKU 2312 Battle City PKU 1010 STAMPS PKU 3051 Satellite Photographs PKU 1154 LETTERS USACO Packing Rectangles USACO Milking Cows PKU 1167 The Buses PKU 1664 放蘋果

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

A Za, A Za, Fighting...

PKU 1190 生日蛋糕

導航

統計

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜