C++: 优化多层生日蛋糕表面积 - 深度优先搜索算法

思路： 首先，我们可以根据题目要求，将体积为Nπ的蛋糕分成M层，每一层都是一个圆柱体。

我们可以使用深度优先搜索（DFS）来枚举每一层的半径和高度，并计算出对应的表面积。在搜索过程中，我们需要满足半径和高度的递减条件，即Ri>Ri+1且Hi>Hi+1。

具体实现如下：

1. 定义一个全局变量minSurface，用来保存最小表面积。
2. 编写一个dfs函数，参数为当前层数、当前体积、当前表面积以及上一层的半径和高度。
3. 在dfs函数中，首先判断当前层数是否大于M，如果大于M，则说明已经搜索完所有层，此时需要更新最小表面积。
4. 在dfs函数中，使用循环枚举当前层的半径和高度，注意半径和高度的递减条件。对于半径，我们可以从上一层的半径开始减小；对于高度，我们可以从上一层的高度开始减小。
5. 在循环中，计算当前层的体积和表面积，并更新当前体积和表面积。
6. 在循环中，如果当前表面积已经大于等于最小表面积，则可以剪枝，不再继续搜索。
7. 在循环中，如果当前体积已经小于等于0，则可以剪枝，不再继续搜索。
8. 在循环中，如果当前层的半径和高度满足条件，则进行递归调用dfs函数，搜索下一层。
9. 在主函数中，调用dfs函数，并输出最小表面积。

代码实现如下：

#include <iostream>
#include <cmath>
using namespace std;

int minSurface = INT_MAX; // 全局变量，保存最小表面积

void dfs(int layer, int volume, int surface, int lastR, int lastH) {
    if (layer > 0) {
        if (volume == 0) {
            minSurface = min(minSurface, surface);
            return;
        }
        if (surface >= minSurface || volume <= 0) {
            return;
        }
    }
    for (int r = lastR - 1; r >= layer; r--) {
        for (int h = lastH - 1; h >= layer; h--) {
            int newVolume = volume - r * r * h;
            int newSurface = surface + 2 * r * h;
            dfs(layer + 1, newVolume, newSurface, r, h);
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    dfs(0, N, 0, INT_MAX, INT_MAX);
    if (minSurface == INT_MAX) {
        minSurface = 0;
    }
    cout << minSurface << endl;
    return 0;
}

提示:

• 深搜、宽搜、深搜剪枝、宽搜剪枝

圆柱公式:

• 体积V=πR2H
• 侧面积A’=2πRH
• 底面积A=πR2