英杰们的蛋糕塔（dfs）（难）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define S(r) ((r) * (r))          // 底面积
 4 #define C(r, h) (2 * (r) * (h))   // 侧面积
 5 #define V(r, h) ((r) * (r) * (h)) // 体积
 6 #define VRC(r, v) (2 * v / (r))   // 根据体积和半径计算侧面积
 7 
 8 // 查表法计算各层的体积与侧面积区间下界
 9 int sumMinV[27], sumMinC[27];
10 
11 const int INF = 0x7ffffff;
12 int v, n, minsur = INF; // 最小表面积
13 
14 //  从最底层到最高层搜索
15 //  从第i层开始搭建表面积最小的蛋糕塔
16 //  其底半径和高的最大值为搜索前一层的半径preR和高preH
17 //! leftV为剩余的总体积，surArea为该塔施工过程中累计的表面积
18 void dfs(int i, int preR, int preH, int leftV, int surArea)
19 {
20     if (i == 0) // 抵达最高层
21     {
22         if (leftV == 0 && surArea < minsur)
23             minsur = surArea;
24         return;
25     }
26     //*********************
27     // 预估此路径剩余体积的最小表面积值，若超过全局变量的最小值，则无需继续搜索
28     if (preR > 1 && VRC(preR - 1, leftV) + surArea >= minsur)
29         return;
30 
31     // 剩余体积小于i层的最小体积，体积余量不足
32     if (leftV < sumMinV[i])
33         return;
34 
35     // 累计表面积 + 最小表面积 > 全局最小表面积
36     if (surArea + sumMinC[i] >= minsur)
37         return;
38     //*********************
39     // 以上3步为剪枝操作
40 
41     // 枚举所有的R和H，深搜
42     for (int r = preR - 1; r >= i; --r)
43     {
44         if (i == n)
45             surArea = S(r); // 最底层的底面积
46 
47         // 确定高度枚举范围的上界
48         int H_max = (1.0 * leftV / S(r)) ; // 剩余体积除以底面积为高
49         if (H_max > preH - 1)
50             H_max = preH - 1; // 高的最大值
51 
52         for (int h = H_max; h >= i; --h)                          // 枚举所有的高，因为至少有i层，所以高的下界是i
53             dfs(i - 1, r, h, leftV - V(r, h), surArea + C(r, h)); // 根据接口传递参数
54     }
55 }
56 
57 int main()
58 {
59     cin >> v >> n;
60     // 从顶层往下层递推计算，最高层为0
61     sumMinV[0] = sumMinC[0] = 0;
62 
63     for (int i = 1; i <= n; ++i)
64     {
65         // 所有半径和高度都是正整数，所以可得下面的递推式
66         sumMinC[i] = sumMinC[i - 1] + C(i, i); // 第i层之上的最小侧面积之和
67         sumMinV[i] = sumMinV[i - 1] + V(i, i); // 第i层之上的最小体积之和
68     }
69 
70     // 最底层最大的H和R
71     // 底半径为n（最小值）的时候h（高度）最大
72     int maxH = (v - sumMinV[n - 1]) / S(n) + 1; // 不加1也能过，为什么？
73     // 高度为1的时候圆柱的半径最大
74     int maxR = sqrt(double((v - sumMinV[n - 1]) + 1)); // 这里也是不加1也能过
75     /*
76     这里加1是为了避免在计算最大底半径时出现精度误差。具体来说，假设最大底半径为maxR，最底层的底面积为S(n)，当前已经搭建的层数为k，累计体积为sumV，那么最大底半径至少需要满足以下条件：
77         S(n) * maxR * maxR <= v - sumV
78 
79     其中，v是总体积，sumV是当前已经搭建的蛋糕塔的总体积。
80     由于计算机在处理浮点数时存在精度误差，因此在计算S(n) * maxR * maxR时可能会出现略微小于v - sumV的情况，导致计算出的maxR比实际值小一些。为了避免这种情况，可以在计算S(n) * maxR * maxR时加上1，使得计算出的maxR略微大于实际值，从而避免精度误差。
81 
82     需要注意的是，这种精度误差通常只会在极端情况下出现，对于大多数情况来说，不加1也不会导致结果错误。因此，这里加1只是为了提高程序的健壮性和鲁棒性。
83     */
84 
85     minsur = INF; // 初始化
86     dfs(n, maxR, maxH, v, 0);
87 
88     if (minsur == INF)
89         cout << 0 << endl;
90     else
91         cout << minsur << endl;
92     return 0;
93 }