信息学奥赛一本通T1441-生日蛋糕 写完之后不想吃蛋糕了

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
// 初始化一个较大的常量值，用于后续比较和更新最小值
int kkk=99999;
// 定义全局变量n和m，分别表示目标体积和块数
int n, m;
// 定义两个数组vv和ss，分别存储体积和表面积的累加值
int vv[50], ss[50];
void dfs(int x, int r, int h, int v, int s) {
    // 如果所有块都处理完毕
    if (x == 0) {
        // 如果当前体积等于目标体积，则更新最小表面积
        if (v == n) {
            kkk = min(kkk, s);
        }
        return;
    }
    // 如果当前体积加上当前块的体积超过目标体积，则返回
    if (v + vv[x] > n) return;
    // 如果当前表面积加上当前块的表面积超过当前最小表面积，则返回
    if (s + ss[x] > kkk) return;
    // 如果当前表面积加上估算的最大可能表面积超过当前最小表面积，则返回
    if (s + 2 * (n - v) / r > kkk) return;
    // 遍历可能的半径和高度组合
    for (int i = min(r - 1, (int)sqrt(n - v)); i >= x; i--) {
        for (int j = min(h - 1, (n - v) / (i * i)); j >= x; j--) {
            // 递归调用dfs函数，处理下一个块
            dfs(x - 1, i, j, v + i * i * j, s + 2 * i * j + (x == m ? i * i : 0));
        }
    }
}
int main() {
    // 输入目标体积和块数
    cin >> n >> m;
    // 计算体积和表面积的累加值
    for (int i = 1; i <= m; i++) {
        vv[i] = vv[i - 1] + i * i * i;
        ss[i] = ss[i - 1] + 2 * i * i;
    }
    // 调用dfs函数，开始深度优先搜索
    dfs(m, 99999, 99999, 0, 0);
    // 如果最小表面积未被更新，输出0；否则输出最小表面积
    if (kkk == 99999) {
        cout << 0 << endl;
    } else {
        cout << kkk << endl;
    }
    return 0;
}