题解:
这道题的关键是找到状态转移方程,从最底层(n)开始,计算上面全部(n, n - 1, n - 2 …… 1)层的总表面积和总体积,从而来确定使表面积最小的S
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 }
标签:英杰,表面积,int,minsur,leftV,dfs,体积,蛋糕,surArea From: https://www.cnblogs.com/nijigasaki14/p/17578663.html