• <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)  編輯 收藏 引用 所屬分類: 題目分類:搜索
            久久久国产精品福利免费| 香蕉久久久久久狠狠色| 久久久www免费人成精品| 亚洲精品午夜国产va久久| 久久久午夜精品| 无码精品久久久天天影视| 99久久国产亚洲高清观看2024| 亚洲人成无码网站久久99热国产| 久久婷婷五月综合97色 | 伊人情人综合成人久久网小说| 久久久久亚洲AV无码专区首JN | 久久精品a亚洲国产v高清不卡| 91精品免费久久久久久久久| 久久影院亚洲一区| 狠狠色丁香久久综合五月| 亚洲伊人久久综合影院| 久久久国产乱子伦精品作者| 久久精品国产福利国产琪琪| 东京热TOKYO综合久久精品| 久久天天躁夜夜躁狠狠| 久久精品国产免费一区| 99精品久久久久久久婷婷| 色播久久人人爽人人爽人人片aV| 99精品久久久久中文字幕| 久久国产精品无码HDAV| 无码人妻久久一区二区三区蜜桃| 日韩AV毛片精品久久久| 久久青草国产手机看片福利盒子| 午夜精品久久久久| 亚洲国产高清精品线久久| 久久久91人妻无码精品蜜桃HD| 日韩精品国产自在久久现线拍| 久久99精品国产麻豆| 久久综合给久久狠狠97色| 亚洲综合伊人久久综合| 久久精品国产亚洲αv忘忧草| 思思久久99热只有频精品66| 亚洲人成电影网站久久| 久久久久久久久久久精品尤物| 一97日本道伊人久久综合影院| 亚洲午夜精品久久久久久app|