该剪枝的链接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

• 不等式的放缩 (15) jndx20111221395 2012-08-14 22:11:19