国产精品丝袜xxxxxxx,国产女人水真多18毛片18精品视频,欧美激情亚洲另类

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 閱讀(524) 評論(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)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜