洛谷 P1731 生日蛋糕

// 第 ① 版：只按题意搜，一个剪枝都不加
//
// 从**最下面那层**往上搜（下面那层最大，先定它，上面的选择范围才被夹住）：
//   · 第 dep 层（还剩 dep 层没定）的半径 R：不超过下面那层的 R − 1，也不超过 √剩余体积；
//     还剩 dep 层，每层至少 1、且严格递减 ⇒ R 至少是 dep。高 H 同理。
//   · 用掉体积 R² × H，攒上侧面积 2 × R × H；最下面那层还要额外算一次上表面 R²
//     （★ 上面每层挡住的那一圈，加起来正好等于最下层的上表面，所以只算一次）。
//
// ⚠ 它是对的，但慢：`N = 20000`、`M = 15` 时本机跑到天荒地老（正文第 ④ 步有实测）。
//
// 输入：第一行 N（体积 Nπ），第二行 M（层数）。

#include <bits/stdc++.h>
using namespace std;

int n, m;
long long best = LLONG_MAX, calls = 0;

/** dep = 还剩几层要定，v = 还剩多少体积，s = 已经攒了多少面积 */
void dfs(int dep, int v, long long s, int maxR, int maxH) {
    calls++;
    if (dep == 0) {
        if (v == 0) best = min(best, s);
        return;
    }
    for (int r = min(maxR, (int)sqrt((double)v)); r >= dep; r--)
        for (int h = min(maxH, (r * r == 0) ? 0 : v / (r * r)); h >= dep; h--) {
            long long add = 2LL * r * h + (dep == m ? (long long)r * r : 0);
            dfs(dep - 1, v - r * r * h, s + add, r - 1, h - 1);
        }
}

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    dfs(m, n, 0, 10000, 10000);
    cout << (best == LLONG_MAX ? 0 : best) << '\n';
    if (argc > 1 && string(argv[1]) == "calls") cerr << "dfs 调用了 " << calls << " 次\n";
    return 0;
}

// 换一把尺子：加剪枝前后各走了多少个节点
//
// ★ 正文第 ④ 步那张表就是它打的。两份实现在同一个文件里跑同一组输入，
//   数的是同一个动作：**dfs 被调用了多少次**。
//
// 用法：./p1731Count <N> <M>          两版都跑
//       ./p1731Count <N> <M> fast     ★ 只跑剪枝版（无剪枝版在某些输入上要几分钟）
//       ./p1731Count <N> <M> csv      只打 `键,值`，给 check:viz 用

#include <bits/stdc++.h>
using namespace std;

int n, m;
long long callsA = 0, bestA = LLONG_MAX;
long long callsB = 0, bestB = LLONG_MAX;
long long minV[20], minS[20];

void dfsA(int dep, int v, long long s, int maxR, int maxH) {
    callsA++;
    if (dep == 0) { if (v == 0) bestA = min(bestA, s); return; }
    for (int r = min(maxR, (int)sqrt((double)v)); r >= dep; r--)
        for (int h = min(maxH, v / (r * r)); h >= dep; h--)
            dfsA(dep - 1, v - r * r * h, s + 2LL * r * h + (dep == m ? (long long)r * r : 0), r - 1, h - 1);
}
void dfsB(int dep, int v, long long s, int maxR, int maxH) {
    callsB++;
    if (dep == 0) { if (v == 0) bestB = min(bestB, s); return; }
    if (v < minV[dep]) return;
    if (s + minS[dep] >= bestB) return;
    for (int r = min(maxR, (int)sqrt((double)v)); r >= dep; r--) {
        if (s + 2LL * v / r >= bestB) return;
        for (int h = min(maxH, v / (r * r)); h >= dep; h--)
            dfsB(dep - 1, v - r * r * h, s + 2LL * r * h + (dep == m ? (long long)r * r : 0), r - 1, h - 1);
    }
}

int main(int argc, char** argv) {
    n = (argc > 1) ? atoi(argv[1]) : 100;
    m = (argc > 2) ? atoi(argv[2]) : 2;
    string mode = (argc > 3) ? argv[3] : "";
    for (int i = 1; i < 20; i++) {
        minV[i] = minV[i - 1] + (long long)i * i * i;
        minS[i] = minS[i - 1] + 2LL * i * i;
    }
    dfsB(m, n, 0, 10000, 10000);
    if (mode != "fast") dfsA(m, n, 0, 10000, 10000);
    if (mode == "csv") {
        cout << "answer," << (bestB == LLONG_MAX ? 0 : bestB) << '\n';
        cout << "callsA," << callsA << '\n';
        cout << "callsB," << callsB << '\n';
    } else {
        cout << "N = " << n << "，M = " << m << "，答案 S = "
             << (bestB == LLONG_MAX ? 0 : bestB) << '\n';
        if (mode != "fast")
            cout << "① 不剪枝    dfs 调用 " << callsA << " 次\n";
        cout << "② 三个剪枝  dfs 调用 " << callsB << " 次\n";
        if (mode != "fast" && callsB)
            cout << "⇒ 差 " << (callsA / callsB) << " 倍\n";
    }
    return 0;
}

// 推荐写法：同一棵搜索树，加三个剪枝
//
// ★ 三个剪枝，一个比一个值钱（正文第 ④ 步逐个量了）：
//
//   ① **体积够不够**：还剩 dep 层，每层至少是 (1..dep) 那样的最小配置，
//      最少也要吃掉 minV[dep] = Σ j³ 的体积。剩下的比它还少 ⇒ 这条路走不通。
//   ② **面积已经亏了**：还剩 dep 层，至少还要糊上 minS[dep] = Σ 2j² 的面积。
//      已攒的 + 它 ≥ 当前最优 ⇒ 再往下不可能更好。
//   ③ ★★ **拿剩余体积估剩余面积**：剩下要糊的侧面积是 Σ 2 Rᵢ Hᵢ，
//      而 Σ Rᵢ² Hᵢ = 剩余体积 v，且每个 Rᵢ 都小于当前的 R
//      ⇒ Σ 2 Rᵢ Hᵢ = Σ 2 Rᵢ² Hᵢ / Rᵢ > 2v / R。
//      **这一条是这道题的分水岭** —— 它把「还没定的那些层」和「已经用掉的体积」绑在了一起。
//
// ⚠ 三个剪枝都不改变答案，只改变「走到哪一步就掉头」。

#include <bits/stdc++.h>
using namespace std;

int n, m;
long long best = LLONG_MAX, calls = 0;
long long minV[20], minS[20];

void dfs(int dep, int v, long long s, int maxR, int maxH) {
    calls++;
    if (dep == 0) {
        if (v == 0) best = min(best, s);
        return;
    }
    if (v < minV[dep]) return;                       // ① 体积不够了
    if (s + minS[dep] >= best) return;               // ② 面积已经亏了
    for (int r = min(maxR, (int)sqrt((double)v)); r >= dep; r--) {
        if (s + 2LL * v / r >= best) return;          // ③ ★★ 拿剩余体积估剩余侧面积
        for (int h = min(maxH, v / (r * r)); h >= dep; h--) {
            long long add = 2LL * r * h + (dep == m ? (long long)r * r : 0);
            dfs(dep - 1, v - r * r * h, s + add, r - 1, h - 1);
        }
    }
}

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i < 20; i++) {
        minV[i] = minV[i - 1] + (long long)i * i * i;
        minS[i] = minS[i - 1] + 2LL * i * i;
    }
    dfs(m, n, 0, 10000, 10000);
    cout << (best == LLONG_MAX ? 0 : best) << '\n';
    if (argc > 1 && string(argv[1]) == "calls") cerr << "dfs 调用了 " << calls << " 次\n";
    return 0;
}