• <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>
            心如止水
            Je n'ai pas le temps
            posts - 400,comments - 130,trackbacks - 0

            對于這一題首先可以想到一些明顯的剪枝策略:

            1、 從下往上數第iRiHi至少為m-i+1,因為要至少保證上面幾層可以有的選擇;

            2、 比已出解大,剪枝;

            3、 假設第i層半徑為Ri、高為Hi,則i+1層半徑最多為Ri-1,高最多為Hi-1,考慮極端的情況,那就是剩余m-i層半徑都為Ri-1,高都為Hi-1,如果這樣還達不到體積n,需要剪枝;

            4、 考慮最小的情況,從i+1層到m層全部為1,如果這樣還大于體積n,需要剪枝;

            5、 1層的情況,極端情況為高是1,此時半徑最大sqrt(n);半徑為1,高最大n,這是搜索的邊界

            6、 假設前i層體積為nowv,表面積為nows,第i層半徑為Ri,則如果2*(n-nowv)/rr+nows>=已出解,需要剪枝。這一點有空將給出證明。

             

            以下是我的代碼:

            #include<stdio.h>
            #include
            <math.h>
            long n,m,ans=200000000;
            void dfs(long dep,long nowv,long nows,long rr,long hh)
            {// 前dep層蛋糕體積為nowv 表面積為nows 第dep層半徑rr 高度hh 
                if(dep>=m)
                
            {
                   
            if(nowv==n&&nows<ans)
                     ans
            =nows;
                   
            return;
                }

                
            if(nowv+(rr-1)*(rr-1)*(hh-1)*(m-dep)<n) return;// 每層最大都達不到體積 
                if(nowv+m-dep>n) return;// 每層最小都超過體積 
                if(2*(n-nowv)/rr+nows>=ans) return;// 不等式放縮法剪枝 
                long i,j;
                
            for(i=rr-1;i>=m-dep;i--)
                  
            for(j=hh-1;j>=m-dep;j--)
                    
            if(nows+2*i*j<ans)// 比已出解小 
                      dfs(dep+1,nowv+i*i*j,nows+2*i*j,i,j);
            }

            int main()
            {
                FILE 
            *fin,*fout;
                
            long i,j;
                fin
            =fopen("cake.in","r");
                fscanf(fin,
            "%ld%ld",&n,&m);
                fclose(fin);
            // Read In
                for(i=m;i<=sqrt(n);i++)
                  
            for(j=m;j<=n;j++)
                   dfs(
            1,i*i*j,i*i+2*i*j,i,j);
                fout
            =fopen("cake.out","w");
                fprintf(fout,
            "%ld\n",ans);
                fclose(fout);
            return 0;
            }

            posted on 2010-01-06 19:44 lee1r 閱讀(1183) 評論(0)  編輯 收藏 引用 所屬分類: 題目分類:搜索
            国产精品九九久久免费视频 | 久久久久久久久无码精品亚洲日韩| 精品99久久aaa一级毛片| 99热精品久久只有精品| 色偷偷91久久综合噜噜噜噜| 99久久香蕉国产线看观香| 久久无码人妻一区二区三区午夜| 久久久精品国产sm调教网站| 99久久国产综合精品五月天喷水| 久久久无码精品亚洲日韩软件| 一本久久a久久精品vr综合| 国产亚洲综合久久系列| 久久婷婷五月综合成人D啪| 亚洲国产精品无码成人片久久| 久久综合狠狠色综合伊人| 一本一道久久a久久精品综合| 国产亚洲精品美女久久久| 理论片午午伦夜理片久久| 久久66热人妻偷产精品9| 亚洲精品高清一二区久久| 久久91精品国产91久久麻豆| 久久亚洲AV成人无码软件| 久久精品国产99国产精偷| 一本大道久久香蕉成人网| 国产一区二区精品久久凹凸| 久久综合给久久狠狠97色| 一本色道久久88—综合亚洲精品| 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲 | 热re99久久6国产精品免费| 精品久久久无码中文字幕天天| 国产精品一久久香蕉国产线看观看| 久久久人妻精品无码一区| 国产高清美女一级a毛片久久w | 嫩草影院久久99| 蜜臀av性久久久久蜜臀aⅴ| 亚洲综合伊人久久大杳蕉| 热久久国产欧美一区二区精品| 狠狠久久综合| 欧美粉嫩小泬久久久久久久 | 亚洲精品tv久久久久久久久 | 久久精品国产精品青草app|