在线亚洲观看,欧美一区2区视频在线观看,在线综合亚洲欧美在线视频

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
4

int mins[25],minv[25],n,m,ms;
5

// 當前層數,下面那層的半徑,高度,剩余體積,所用的面積
7

void 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

int 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 閱讀(459) 評論(0) 編輯收藏引用

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



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

pku 1190

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜