生日蛋糕

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 1398 字
自底向上 DFS 配体积与面积下界剪枝
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1441
// 题意：要做体积为 N * PI 的 M 层圆柱形蛋糕，半径和高度从下往上严格递减，求外表面（不含最下层底面）面积 Q = S * PI 中 S 的最小值，无解输出 0。
// 思路：自底向上 DFS + 可行性/最优性剪枝。
// 1. 预处理 minv[i]、mins[i]：i 层蛋糕的最小体积与最小侧面积，用于体积下界和面积下界剪枝。
// 2. 露出的所有上表面恰好拼成最底层的一个圆，所以总面积 = 各层侧面积之和 + 最底层半径的平方。
// 3. 再用「剩余体积按当前半径估算侧面积」剪掉不可能更优的分支。
// 复杂度：搜索空间经剪枝后很小，约 O(状态数) 时间 / O(M) 空间
// 易错点：S 里要加上最底层半径的平方（顶面），只算侧面积会偏小。
// 易错点：搜索时半径和高度的枚举下界都至少为该层剩余层数，否则上面几层放不下。
#include <bits/stdc++.h>
using namespace std;
int N, M;
int minv[25], mins[25];
int best = 1e9;
void dfs(int left, int r0, int h0, int v, int s){
    if(left == 0){
        if(v == N) best = min(best, s);
        return;
    }
    if(v + minv[left] > N) return;
    if(s + mins[left] >= best) return;
    if(s + 2 * (N - v) / r0 >= best) return;
    for(int r = r0 - 1; r >= left; r--){
        int maxh = min(h0 - 1, (N - v - minv[left - 1]) / (r * r));
        for(int h = maxh; h >= left; h--){
            int nv = v + r * r * h;
            int ns = s + 2 * r * h;
            if(left == M) ns += r * r;
            dfs(left - 1, r, h, nv, ns);
        }
    }
}
int main(){
    if(!(cin >> N)) return 0;
    if(!(cin >> M)) return 0;
    for(int i = 1; i <= M; i++){
        minv[i] = minv[i - 1] + i * i * i;
        mins[i] = mins[i - 1] + 2 * i * i;
    }
    dfs(M, (int)sqrt(N) + 1, N + 1, 0, 0);
    if(best == 1e9) best = 0;
    cout << best << "\n";
    return 0;
}
生日蛋糕

正文

一本通·提高篇的其它内容
