• <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)  編輯 收藏 引用 所屬分類: 題目分類:搜索
            久久国产色av免费看| 精品一二三区久久aaa片| 国产精品女同一区二区久久| 久久人人爽人人爽人人av东京热 | 久久无码专区国产精品发布| 国内精品久久久久影院日本| 久久久久人妻一区精品性色av | 国内精品久久久久久久久| 精品久久久久久亚洲精品| 999久久久免费精品国产| 99精品久久精品| 国产福利电影一区二区三区久久老子无码午夜伦不| 久久人人爽人人人人爽AV| 亚洲七七久久精品中文国产 | 精品久久久久久99人妻| 亚洲精品无码专区久久久| 精品久久久噜噜噜久久久 | 久久亚洲国产午夜精品理论片| 久久久久久国产精品无码下载| 国内精品伊人久久久久777| 精品久久久久久久| 国产午夜精品久久久久九九电影| 久久久久久久久久免免费精品| 久久只有这精品99| 精品久久久久久国产牛牛app| 中文无码久久精品| 97久久精品人人澡人人爽| 亚洲午夜久久久久久噜噜噜| 久久性精品| 精品免费久久久久国产一区| 亚洲AV无码久久精品蜜桃| 久久精品国产一区二区三区| 99久久婷婷国产综合亚洲| A狠狠久久蜜臀婷色中文网| 中文字幕亚洲综合久久| 久久精品国产亚洲77777| 伊人久久久AV老熟妇色| 久久国产精品免费一区| 久久久精品午夜免费不卡| 99久久免费国产特黄| 99热成人精品热久久669|