题目地址:http://poj.org/problem?id=1190
一道很有趣的搜索题……主要是剪枝……
我弄了5个剪枝:
1.当前剩余层数>=上层半径,剪掉
2.当前剩余层数>=上层高度,剪掉
3.体积<1,剪掉
4.体积<当前可能的最小体积(我用等差数列求和公式算的……也不知道对不对)
5.神奇剪枝网上看的,当前(剩余体积*2)/上层半径+当前表面积总和>当前搜出的最优解,剪掉
代码很简单,20行
1 #include
2 #include
3 #include
4 #define pow2(k) k*k
5 #define v(r,h) pow2(r)*h
6 #define min(a,b) am){if(!lv)s=min(s,ans);return;}if(r<=m-c+1||h<=m-c+1||ans+lv*2/r>s||lv<1||lv<(m-c+2)*(m-c+1)/2)return;
12 for(int i=r-1;i>0;i--)for(int j=1;j
18 for(int i=beg;i>=1;i--)for(int j=1;v(i,j)<=n;j++)dfs(i,j,2,n-v(i,j),pow2(i)+2*i*j);
19 cout<<(s==INT_MAX?0:s);
20 return 0;
21 }
手机扫一扫
移动阅读更方便
你可能感兴趣的文章