AcWing 168.生日蛋糕

题目链接

思路

大体思路

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

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

图示

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

剪枝优化

1.优化搜索顺序

1. 层间：从下到上
2. 层内：先枚举半径再枚举高（半径相对于高来说对体积的影响较大），半径由大到小，高度由大到小

2. 可行性剪枝

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

1. 对于R, 当前为第u层, 第u层的体积为$V_u$。R最小的取值应该是当前的层号u ，R的最大值应该由两部分决定
   • u+1层的半径减1, 记$R_{u+1}?1$
   • 第u层体积的最大值除第u层高度的最小值u

这两者的最小值, 故有以下等式成立
u≤Ru≤min{Ru+1?1,n?min∑i=1u?1Vi?Vu}u \leq R_u \leq min \lbrace R_{u+1}-1, \sqrt{\frac{n-min\sum_{i=1}^{u-1}V_i - V}{u}} \rbraceu≤Ru?≤min{ Ru+1??1,un?min∑i=1u?1?Vi??V? ?}

2. 对于第u层高度h的推导同理，高度h的取值的最小值应该大于等于层号u，高度的最小值由两部分决定
   • $H_{u+1}?1$
   • 第u层体积的最大值除第u层的底面积最小值

故同理可得出下列等式
u≤Hu≤min{Hu+1?1,n?min∑i=1u?1Vi?VRu2}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} \rbraceu≤Hu?≤min{ Hu+1??1,Ru2?n?min∑i=1u?1?Vi??V?}

4. 考虑体积的剪枝：预处理前u层的体积最小值$min{\sum }_{i=1}^{u?1}{V}_i$, 会有$V+min{\sum }_{i=1}^{u?1}{V}_i\le n$

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

   第一层到第u层的表面积有（不考虑$\pi$）
   $$S_{1?u}=2\sum _{i=1}^u{R}_i{H}_i=\frac{2}{R_{u+1}}\sum _{i=1}^u{R}_{u+1}{R}_i{H}_i>\frac{2}{R_{u+1}}\sum _{i=1}^u{R}_i^2{H}_i$$
   第一层到第u层的体积有
   $$n?V=\sum _{i=1}^u{R}_i^2{H}_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}$时就可以剪枝掉（最优性剪枝)

3.最优性剪枝

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

4.排除等效冗余

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

代码

#include<iostream>
#include<cmath>
using namespace std;const int N = 24, INF = 1e9;int n, m;
int minv[N], mins[N];
int res = INF;//记录每层的半径和高，因为会用到上一层的高度
int R[N], H[N];//u当前层次，v当前处理的体积和，s当前处理的面积和
void dfs(int u, int v, int s)
{
    if(v + minv[u] > n) return;if(s + mins[u] >= res) return;if (s + 2 * (n - v) / R[u + 1] >= res) return;if(!u){
    if(v == n) res = s;return;}//搜索顺序，先R后H，从大到小for(int r = min(R[u + 1] - 1,(int)sqrt((n - v - minv[u - 1]) / u)); r >= u; r--)for(int h = min(H[u + 1] - 1, (n - v - minv[u - 1]) / r / r); h >= u; h--){
    H[u] = h, R[u] = r;//最底层的时候需要加上r*rint t = u == m ? r * r : 0;dfs(u - 1, v + r * r * h, s + 2 * r * h + t);}
}int main()
{
    cin >> n >> m;for(int i = 1; i <= m; i++){
    minv[i] = minv[i - 1] + i * i * i;mins[i] = mins[i - 1] + 2 * i * i;}//m+1层不存在，作为哨兵，减少边界情况的判断R[m + 1] = H[m + 1] = INF;dfs(m, 0, 0);if(res == INF) res = 0;cout << res << endl;return 0;
}