| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
说说最重要的剪枝的数学含义该剪枝的链接http://poj.org/showmessage?message_id=161606 2*leftVolume/r+currentS>=min currentS代表“已有的圆柱的侧面积之和+最底下圆柱的横截面面积”。min代表已得到的最小表面积。 假设只有一个圆柱,该圆柱的半径为r,体积为leftVolume,那么根据体积和表面积公式,可知:2 * leftVolume/r 是该圆柱的侧面积。 现在我们有2个圆柱,要求这两个圆柱叠在一起之后满足题目的条件:下柱半径>上柱半径。把上柱压扁,压到和下柱的半径相等,那么根据表面积和体积公式,我们知道上柱的侧面积会减小。 多个圆柱叠立,假设最下面圆柱半径最大,该半径为r。于是,这些圆柱的侧面积之和>=等体积的半径为r的圆柱的侧面积。 回到该剪枝。假设还有k层柱要搜索,leftVolume是剩余体积,r是第k层的圆柱的最大可能半径。那么2*leftVolume/r<=k层圆柱的最小侧面积之和。 所以,当2*leftVolume/r+currentS>=min时,就没必要再往下搜了。 上述关于该剪枝合理性的说法如果还有模糊的地方,欢迎大家补充。 这个剪枝的效果非常好。只用它,再配合r和h的模糊范围,就不会超时了。问题是,我想不通为什么它的效果会这么好。如果有人知道,麻烦你用站内邮件告诉我,非常感谢! mzhang87 Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator