生日蛋糕 - 深度优先搜索剪枝技巧优化

"问题 B: 【一本通提高篇深搜的剪枝技巧】生日蛋糕\n[题目描述]\n7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。\n\n设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i<M时，要求Ri>Ri+1且Hi>Hi+1。\n\n由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。\n\n令Q= Sπ\n\n请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。\n\n（除Q外，以上所有数据皆为正整数）\n\n输入\n有两行，第一行为N（N<=10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M<=20)，表示蛋糕的层数为M。\n\n输出\n仅一行，是一个正整数S（若无解则S=0）。\n\n样例输入\n100 2\n样例输出\n68\n提示\n附：圆柱公式\n\n\n体积V=πR2H\n\n侧面积A’=2πRH\n\n底面积A=πR2\n\n内容：【思路分析】\n这是一个组合优化问题，需要找到一种制作方案，使得蛋糕的外表面积最小。根据题目要求，可以得到以下几点信息：\n1. 蛋糕的总体积为Nπ，每一层的体积都是已知的。\n2. 蛋糕的每一层都是一个圆柱体，底面积和侧面积都是已知的。\n3. 蛋糕的每一层的半径和高度都是正整数，且满足一定的大小关系。\n\n为了使蛋糕的外表面积最小，可以考虑以下两个因素：\n1. 选择合适的半径和高度，使得每一层的侧面积最小。\n2. 选择合适的半径和高度，使得每一层的底面积最小。\n\n因此，可以使用深度优先搜索（DFS）来穷举所有可能的制作方案，然后计算每一种方案的外表面积，找到最小的面积值。\n\n【算法步骤】\n1. 定义一个全局变量min_surface，用于保存最小的外表面积。\n2. 使用DFS搜索，从第一层开始逐层选择半径和高度。\n3. 在DFS的过程中，根据题目要求，剪枝掉一些不符合条件的分支，以减少搜索空间。\n4. 在DFS到达最后一层时，计算当前方案的外表面积，并更新min_surface的值。\n5. 最后输出min_surface的值。\n\n【代码实现】\npython\nimport math\n\ndef dfs(N, M, cur_layer, cur_volume, cur_surface, max_r, max_h):\n global min_surface\n if cur_layer > M: # DFS到达最后一层\n if cur_volume == N: # 如果当前方案的体积等于目标体积\n min_surface = min(min_surface, cur_surface) # 更新最小的外表面积\n return\n \n for r in range(max_r-1, 0, -1): # 从大到小选择半径\n for h in range(max_h-1, 0, -1): # 从大到小选择高度\n if cur_volume + math.pi * r * r * h > N: # 当前方案的体积已经超过目标体积，剪枝\n continue\n if 2 * math.pi * r * h + cur_surface >= min_surface: # 当前方案的外表面积已经大于最小外表面积，剪枝\n continue\n if cur_layer != 1 and cur_surface + math.pi * r * r + 2 * math.pi * r * h >= min_surface: # 当前方案的前几层的外表面积已经大于最小外表面积，剪枝\n continue\n \n dfs(N, M, cur_layer+1, cur_volume + math.pi * r * r * h, cur_surface + 2 * math.pi * r * h, r, h) # 继续DFS到下一层\n\ndef main():\n N, M = map(int, input().split())\n global min_surface\n min_surface = float('inf') # 初始化最小外表面积为正无穷大\n dfs(N, M, 1, 0, 0, int(math.sqrt(N / M)), N // M) # 从第一层开始DFS，初始半径的上限为sqrt(N/M)，初始高度的上限为N/M\n if min_surface == float('inf'): # 如果没有找到合法的方案\n min_surface = 0\n print(min_surface)\n\nif __name__ == '__main__':\n main()\n\n\n【复杂度分析】\n该算法的时间复杂度为O(N^2 * M)，其中N为蛋糕的体积，M为蛋糕的层数。在DFS的过程中，每一层选择半径和高度的时间复杂度为O(N/M)。整个DFS的时间复杂度为O(N^2 * M)。空间复杂度为O(M)，用于保存每一层的半径和高度。