AcWing 168. 生日蛋糕【图解+推导】

记最底层为m,很容易观察得出，表面积的公式为 $$S_总 = S_{m层上侧面积} + \sum_{i=1}^{m}2\pi R_iH_i$$ 而体积为 $$V_总= \sum_{i=1}^{m}\pi R_i^2H_i$$

有了两个公式，还有题目给出的每层最小高度和最小半径，就知道可以用剪枝+暴搜来做这个题

这个图对理解下面公式有帮助

记总体积为n，当前层位u, 第u层的高度为$H_u$, 半径为$R_u$， 体积为$V_u$, 第$m$层到第u层体积的累计值$V$

这两者的最小值, 故有以下等式成立 $$ u \leq R_u \leq min \lbrace R_{u+1}-1, \sqrt{\frac{n-min\sum_{i=1}^{u-1}V_i - V}{u}} \rbrace$$

故同理可得出下列等式 $$ u \leq H_u \leq min \lbrace H_{u+1}-1, \frac {{n-min\sum_{i=1}^{u-1}V_i - V}}{R_u^2} \rbrace$$

考虑体积的剪枝：预处理前u层的体积最小值$min\sum_{i=1}^{u-1}V_i$, 会有$V + min\sum_{i=1}^{u-1}V_i \leq n$

推表面积公式和体积公式的关系

第一层到第u层的表面积有（不考虑$\pi$） $$S_{1-u} = 2\sum_{i=1}^{u}R_iH_i = \frac{2}{R_{u+1}} \sum_{i=1}^{u}R_{u+1}R_iH_i > \frac{2}{R_{u+1}}\sum_{i=1}^{u}R_i^2H_i$$ 第一层到第u层的体积有 $$n - V = \sum_{i=1}^{u}R_i^2H_i$$ 所以惊奇地发现 $$S_{1-u} >\frac{2(n-V)}{R_{u+1}}$$ 因此$S_总=S + S_{1-u}>=S_{ans}$，即$S + \frac{2(n-V)}{R_{u+1}} >= S_{ans}$时就可以剪枝掉（最优性剪枝)

记第$m$层到第u层表面积的累计值$S$, 第1到第$u-1$层表面积的最小值为 $min\sum_{i=1}^{u-1}S_i$ 则应该有$S + min\sum_{i=1}^{u-1}S_i < res$

至此，所有的剪枝都已经考虑清楚，码代码应该不是什么大问题