午夜精品久久久久成人,高清免费久久午夜精品,伊人久久大香线焦综合四虎

堅信：勤能補拙

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

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

相關(guān)文章: 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 放蘋果

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

A Za, A Za, Fighting...

PKU 1190 生日蛋糕

導(dǎo)航

統(tǒng)計

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜