青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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
 4int mins[25],minv[25],n,m,ms;
 5
 6//       當前層數,下面那層的半徑,高度,剩余體積,所用的面積
 7void 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
32int 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)  編輯 收藏 引用

<2009年8月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            国模 一区 二区 三区| 在线一区二区日韩| 一本在线高清不卡dvd| 亚洲青色在线| 日韩亚洲一区在线播放| 夜夜爽www精品| 亚洲一级免费视频| 亚洲欧美日韩国产综合精品二区| 亚洲深夜激情| 久久九九免费视频| 亚洲国产一区二区视频| 亚洲大片av| 洋洋av久久久久久久一区| 亚洲一级二级在线| 久久亚洲综合网| 欧美日韩蜜桃| 国产亚洲一区二区三区| 亚洲日本中文字幕| 西瓜成人精品人成网站| 麻豆精品视频在线| 一区二区三区视频观看| 久久riav二区三区| 欧美日韩一区二区在线播放| 国模私拍视频一区| 在线午夜精品自拍| 老司机凹凸av亚洲导航| 99视频精品在线| 久久一区中文字幕| 国产精品一二| 99精品福利视频| 久久久久www| 一区二区三区免费在线观看| 久久久久国产精品厨房| 欧美亚日韩国产aⅴ精品中极品| 激情文学综合丁香| 亚洲欧美区自拍先锋| 亚洲第一视频| 欧美专区日韩视频| 国产精品三区www17con| 夜夜嗨av一区二区三区四季av| 久久亚洲精品网站| 亚洲综合国产| 美女啪啪无遮挡免费久久网站| 亚洲精品国产无天堂网2021| 亚洲在线观看免费| 欧美激情一区| 久久国产主播精品| 国产精品亚洲一区| 在线中文字幕不卡| 亚洲国产日韩欧美在线图片| 久久久久久久999精品视频| 国产精品午夜视频| 亚洲午夜精品久久久久久浪潮| 亚洲第一精品电影| 美女性感视频久久久| 国产一区香蕉久久| 久久国产精品毛片| 午夜精品福利在线| 国产精品国产三级国产专播品爱网 | 亚洲欧美日韩另类精品一区二区三区| 欧美成人精品不卡视频在线观看| 韩国精品主播一区二区在线观看| 欧美一区二区三区四区夜夜大片| 亚洲一区二区三区乱码aⅴ| 国产精品久久久久av| 午夜国产精品视频免费体验区| 亚洲淫性视频| 国产综合婷婷| 欧美顶级大胆免费视频| 欧美福利小视频| 一本一本久久| 亚洲一区二区黄色| 国产最新精品精品你懂的| 久久免费少妇高潮久久精品99| 久久久99爱| 99国产成+人+综合+亚洲欧美| 一区二区三区四区国产| 国产视频自拍一区| 亚洲国产高清一区| 欧美日韩一级片在线观看| 亚洲免费网站| 久久久久久9999| 夜夜嗨av一区二区三区四季av| 在线亚洲自拍| 在线日韩成人| 在线综合亚洲| 伊人久久婷婷| 一区二区三区精品视频在线观看| 国产精品一级久久久| 欧美激情视频免费观看| 国产精品久久一区主播| 玖玖精品视频| 国产精品观看| 亚洲第一黄色| 国产一区二区三区丝袜| 亚洲国产视频一区| 午夜视频久久久| 亚洲黄色高清| 午夜精品久久久久久久| 亚洲精品国产精品国产自| 亚洲在线成人| 一区二区三区|亚洲午夜| 欧美在线中文字幕| 亚洲午夜精品一区二区| 裸体歌舞表演一区二区| 久久精品盗摄| 国产精品午夜久久| 99成人在线| 亚洲精品乱码久久久久久蜜桃91 | 国产午夜精品久久久久久久| 亚洲国产成人高清精品| 国产一区在线免费观看| 亚洲久久视频| 亚洲精品乱码久久久久久久久| 欧美一区二区在线播放| 亚洲一区成人| 欧美区在线观看| 欧美国产亚洲视频| 国内精品福利| 亚洲免费在线观看视频| 亚洲香蕉网站| 欧美黄色影院| 欧美大片在线观看一区二区| 国产亚洲一级| 欧美一区二区三区在线看| 亚洲一级黄色av| 欧美日韩精品免费在线观看视频| 欧美二区在线观看| 亚洲二区精品| 久久亚洲不卡| 免费久久精品视频| 亚洲承认在线| 欧美mv日韩mv国产网站app| 欧美α欧美αv大片| …久久精品99久久香蕉国产 | 亚洲欧美影院| 国产精品二区三区四区| 99综合精品| 亚洲欧美日韩一区二区在线| 国产精品a久久久久久| 99pao成人国产永久免费视频| 一区二区三区 在线观看视频 | 老色批av在线精品| 欧美顶级大胆免费视频| 亚洲日本黄色| 欧美久久一级| 一区二区三区欧美| 欧美一区观看| 激情成人亚洲| 欧美国产欧美亚州国产日韩mv天天看完整| 欧美成年人在线观看| 日韩午夜中文字幕| 国产精品久久久久久影视| 亚洲欧美日韩区| 噜噜噜在线观看免费视频日韩| 在线日韩av片| 欧美 日韩 国产一区二区在线视频 | 久久久久久久久久看片| 乱中年女人伦av一区二区| 亚洲电影视频在线| 欧美日韩三区| 午夜国产欧美理论在线播放| 裸体歌舞表演一区二区| 日韩亚洲欧美一区二区三区| 欧美午夜无遮挡| 久久精品一本久久99精品| 亚洲激情网站| 欧美一区二区在线播放| 亚洲第一天堂av| 欧美三级精品| 久久久精品tv| 一区二区三区日韩欧美| 久久综合给合| 亚洲天堂黄色| 亚洲第一在线视频| 国产精品美女黄网| 嫩模写真一区二区三区三州| 亚洲尤物在线| 亚洲日本一区二区三区| 久久久国产精品亚洲一区 | 欧美久久一区| 久久精品国产成人| 99在线精品免费视频九九视| 久久综合伊人77777蜜臀| 一区二区三区福利| 在线观看亚洲视频| 国产精品久久一卡二卡| 欧美高清视频一区二区| 欧美一区二区在线视频| 在线亚洲国产精品网站| 亚洲二区视频在线| 美国十次了思思久久精品导航| 亚洲欧美另类综合偷拍| 一区二区高清在线| 亚洲精品一品区二品区三品区| 激情小说另类小说亚洲欧美 | 亚洲第一搞黄网站| 理论片一区二区在线| 久久精品人人做人人综合| 亚洲欧美日韩国产另类专区|