POJ 1190 生日蛋糕(DFS:优化剪枝)
http://poj.org/problem?id=1190
7月17日是Mr.W的生日,ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕,每层都是一个圆柱体。
设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时,要求Ri > Ri+1且Hi > Hi+1。
由于要在蛋糕上抹奶油,为尽可能节约经费,我们希望蛋糕外表面(最下一层的下底面除外)的面积Q最小。
令Q = Sπ
请编程对给出的N和M,找出蛋糕的制作方案(适当的Ri和Hi的值),使S最小。
(除Q外,以上所有数据皆为正整数)
Input
有两行,第一行为N(N <= 10000),表示待制作的蛋糕的体积为Nπ;第二行为M(M <= 20),表示蛋糕的层数为M。
Output
仅一行,是一个正整数S(若无解则S = 0)。
Sample Input
100
2
Sample Output
68
Hint
圆柱公式
体积V = πR2H
侧面积A' = 2πRH
底面积A = πR2
分析:
首先我们令最下面一层为第M层,然后最上面一层是第1层.那么我们知道从下到上,每层的圆柱体半径R和H都是整数且都递减.
初始我们给出体积为V,层数为M,所以我们知道第M层的半径R>=M且H>=M,所以我们可以通过第M层圆柱的体积R^2*H_max=Vm<V 得出第M层高H的最大值H_max<V/(R*R)+1 ,同理可以退出R_max<srqt(V/M)+1.
到这里我们有了H和R的上界了.我们在求出sumv[i]表示从第一层到第i层的体积和最小值.以及sums[i]表示从第一层到第i层的侧面积和最小值.
下面就是dfs了,我们令dfs(int floor,int preR,int preH,int leftV,intS)表示当前在第floor层,前一层floor+1时我们取了半径为preR,高为preH.到了floor层我们还剩下leftV体积未分配,且我们已经产生了S的面积.
dfs的终态是:floor=0且leftV正好==0时,如果S的值< ans ,那么我们就用S去更新ans.
当然dfs中还需要剪枝了.
第一个剪枝是:
if((preR>1)&& 2 * vLeft/(preR-1)+ s>=ans)
这句话的含义是如果剩下的体积只做成一个圆柱体的话,得到的侧面积是最少的,且如果这样的话最后的总侧面积还是大于ans ,那么我们可以不用求下面的dfs了,无用功.
第二个剪枝就是:
if(vLeft-sumV[floor]<0||s+sumS[floor]>=ans)
剩余的体积不足,或者面积已经超了.
AC代码:
#include<cstdio>
#include<cmath>
using namespace std;
int V,M;
int ans=65535;
int sumV[21],sumS[21];
void dfs(int floor,int preR,int preH,int leftV,int s)
{
if(floor==0)
{
if(leftV==0&&s<ans) ans=s;
return ;
}
if(preR>1 && 2*(leftV/(preR-1))+s>=ans) return;
if(leftV<sumV[floor] || s+sumS[floor]>=ans) return;
for(int r=preR-1;r>=floor;r--)
{
if(floor==M) s=r*r;
int H_max=(1.0*leftV/(r*r))+1;
if(H_max>preH-1) H_max=preH-1;
for(int h=H_max;h>=floor;h--)
dfs(floor-1,r,h,leftV-r*r*h,s+2*r*h);
}
}
int main()
{
scanf("%d%d",&V,&M);
sumV[0]=sumS[0]=0;
for(int i=1;i<=20;i++)//最多20层
{
sumV[i]=sumV[i-1]+i*i*i;
sumS[i]=sumS[i-1]+2*i*i;
}
int R_max=sqrt(1.0*V/M)+1;
int H_max=(1.0*V/(M*M))+1;
dfs(M,R_max,H_max,V,0);
if(ans==65535) ans=0;
printf("%d\n",ans);
}
分享到:
相关推荐
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
poj生日蛋糕解题报告,希望能够对大家能够有所帮助,不多说了,大家下载
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练)
POJ 1300 Door Man:无向图、欧拉定理、gets、sscanf
北大POJ1020-Anniversary Cake 解题报告+AC代码
POJ上的DP分类: 容易: 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵,求...
北大POJ初级题-数据结构:解题报告+AC代码
poj还是leetcode ProgrammingCompetionCareer 大学的竞赛生涯结束了,抽时间整理了一部分曾经在OJ刷过的题,还有一些找不到了,或者是因为杂物太多(除了代码以外还有题解的pdf、题目的测试数据等等),不想整理了就...
DFS POJ 2488 POJ 3083 POJ 3009 POJ 1321 BFS POJ 3278 POJ 1426 POJ 3126 POJ 3414 POJ 2251 简单搜索技巧和剪枝 POJ 1010 :star: POJ 2362 POJ 1011(搜索+剪枝) POJ 1416 POJ 2676 POJ 1129:white_question_...
poj 2820 古代密码 http://poj.grids.cn/problem?id=2820 可直接运行
poj1002 source code input: The input will consist of one case. The first line of the input specifies the number of telephone numbers in the directory (up to 100,000) as a positive integer alone on ...
本人整理的POJ解题报告,一共有250道题
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
网上整理的一些poj刷题指南。 poj地址:http://poj.org
poj与leetcode