mostshadow

用户名：most2022

访问量：2060

签　名：

等　　级
排　　名	4280
经　　验	1728
参赛次数	0
文章发表	7
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

Java 重写Arrays.sort()的排序规则
浏览：168

你可能喜欢

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

信息学奥赛一本通T1441-生日蛋糕（JAVA+详细分析）

　　作者: mostshadow　　　　发表时间：2022-01-25 16:26:06 浏览：674　|　评论：0　

原题链接：信息学奥赛一本通T1441-生日蛋糕

**题目解析**：给出蛋糕的总体积 n 和蛋糕层数 m，求最佳的各层蛋糕的半径和高度分配方案，使得蛋糕表面积最小。

**题目条件理解**：对各层蛋糕进行编号，自下而上，最底层编号为1，最高一层编码为m。对于半径和高度存在约束，Ri > Ri+1   和 Hi > Hi+1。
   蛋糕表面积的相关计算：
   第1层~第m层顶端表面积（即圆柱体上表面）**等价于** 第1层的底面面积
   **总表面积 = 第1层的底面面积 + sum（第1层~第m层的侧面积）**

**问题求解**：
这是一道搜索类型的题目，常规做法是从第一层蛋糕开始，逐层向上搜索，直至搜索到最优解。
但是第一层蛋糕的半径和高度没有明确给出上下限，需要我们自己推导。
由于第i+1层蛋糕的半径和高度 必须大于 第i层蛋糕的半径和高度，由此可推导出**第1层蛋糕半径的下限**为m。（注：极端情况下，第一层的半径为1，第二层的半径为2，...，第m层的半径为m）
同理，**第1层的高度的下限为m**。
那第一层的半径上限如何确定呢？这个需要借助已经给出的蛋糕总体积n，我们的想法是从第一层开始逐层枚举，那么第2层~第m层同样是会占据一部分体积，那么要求第一层在分配的时候，不能把体积都分配完，所以由此推出**第一层蛋糕半径的上限**：`r * r * m <= n`（注：r为待枚举的第一层半径高度）。
同理，**第1层的高度的上限**：`r * r * h <= n`（注：h为待枚举的第一层高度）。
下面给出搜索框架：
```java
for(int r = m; r * r * m <= n; r++){
    for(int h = m; r * r * h <= n; h++){
        if(r * r + 2 * r * h < ans){//只有有机会搜索到更优的解进行递归
            
            //确定第一层蛋糕的半径和高度，逐层往上搜索
            //dfs()细节待补充
            dfs();
        }
    }
}
```

接下来谈谈如果逐层搜索以及如何剪枝。
```java
public static void dfs(int depth, int v, int s, int r, int h){
    //暂时不考虑剪枝的细节
    
    //由于第i+1层的高度和半径 < 第i层的高度和半径
    //故第i+1层的高度和半径的下限分别为r-1;(此处r为第i层的半径, h为第i层的高度)
    //由于必须保证第m层的最小半径和高度为1,所以借此确定第i+1层的半径和高度的上限
    //并且需要判断当前选取的半径i和高度j不能超过总体积和小于最优解，才可再往上一层搜索
    for (int i = r -1 ; i >= m - depth; i--){
        for (int j = h - 1; j >= m - depth; j--){
            if((i * i * j + v <= n) && (s + 2 * i * j < ans)){
                dfs(depth + 1, v + i * i * j, s + 2 * i * j, i ,j);
            }
        }
    }
}
```
如果不考虑剪枝，直接爆搜，会超时，所以加入两个剪枝操作。	
● 假设现在搜索到第 depth 层，接下来的 M - depth层的高度和半径均取最大值 h-1 和 r-1，仍然小于总体积n，则剪枝，代码为：`v + (r-1)*(r-1)*(h-1)*(m-depth) < n`。（注：v为搜索到第 depth 层累计的体积，r 和 h 为 第 depth层所确定的半径和高度）
● 假设现在搜索到第 depth 层，接下来的 M - depth层的高度和半径均取最小值1，仍然大于总体积n，则剪枝，代码为：`v + m - depth > n`。（注：v为搜索到第 depth 层累计的体积，r 和 h 为 第 depth层所确定的半径和高度，在代码处做了化简，原始代码：`v + 1 * 1 * 1 *m - depth > n`）

**完整代码**：
```java
import java.util.*;
public class Test{
    public static int n, m;
    public static int ans = Integer.MAX_VALUE;
    public static void dfs(int depth, int v, int s, int r, int h){
        if(depth == m){
            if(v == n){
                ans = s;
            }
            return;
        }
        if(v + (r-1)*(r-1)*(h-1)*(m-depth) < n){
            return;
        }
        if(v + m - depth > n){
            return;
        }

for (int i = r -1 ; i >= m - depth; i--){
            for (int j = h - 1; j >= m - depth; j--){
                if((i * i * j + v <= n) && (s + 2 * i * j < ans)){
                    dfs(depth + 1, v + i * i * j, s + 2 * i * j, i ,j);
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

for(int r = m; r * r * m <= n; r++){
            for(int h = m; r * r * h <= n; h++){
                if(r * r + 2 * r * h < ans){
                    dfs(1, r * r * h, r * r + 2 * r * h, r, h);
                }
            }
        }
        System.out.println(ans);

}
}
```

**参考资料**：https://blog.csdn.net/qq_42367531/article/details/85055165?utm_term=%E4%B8%80%E6%9C%AC%E9%80%9A1674%E5%A0%86%E8%9B%8B%E7%B3%95&utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2~all~sobaiduweb~default-0-85055165&spm=3001.4430

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

mostshadow

TA的其他文章

你可能喜欢

C二级辅导-等差数列（C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

Lucky Word （C++代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

信息学奥赛一本通T1441-生日蛋糕（JAVA+详细分析）

评论区

精彩推荐

C二级辅导-求偶数和（C语言代码）

C二级辅导-计负均正（C语言代码）

时间转换（Java代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

打水问题（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言训练-自由落体问题（C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

Hello, world! （C语言代码）

mostshadow

TA的其他文章

你可能喜欢

C二级辅导-等差数列 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

Lucky Word （C++代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

【明明的随机数】 （C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

信息学奥赛一本通T1441-生日蛋糕（JAVA+详细分析）

评论区

精彩推荐

C二级辅导-求偶数和 （C语言代码）

C二级辅导-计负均正 （C语言代码）

时间转换 （Java代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

打水问题 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言训练-自由落体问题 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

Hello, world! （C语言代码）

C二级辅导-等差数列（C语言代码）

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

　　评论区

C二级辅导-求偶数和（C语言代码）

C二级辅导-计负均正（C语言代码）

时间转换（Java代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

打水问题（C语言代码）

C语言训练-自由落体问题（C语言代码）