[数据结构与算法]168. 生日蛋糕

7 月 17 日是 Mr.W 的生日，ACM-THU 为此要制作一个体积为 Nπ 的 M 层生日蛋糕，每层都是一个圆柱体。

设从下往上数第 i 层蛋糕是半径为 Ri，高度为 Hi 的圆柱。

当 i<M 时，要求 Ri>Ri+1 且 Hi>Hi+1。

由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积 Q 最小。

令 Q=Sπ ，请编程对给出的 N 和 M，找出蛋糕的制作方案（适当的 Ri 和 Hi 的值），使 S 最小。

除 Q 外，以上所有数据皆为正整数。

输入格式

输入包含两行，第一行为整数 N，表示待制作的蛋糕的体积为 Nπ。

第二行为整数 M，表示蛋糕的层数为 M。

输出格式

输出仅一行，是一个正整数 S（若无解则 S=0）。

数据范围

1≤N≤10000,
1≤M≤20

输入样例：

100
2

输出样例：

68

代码：

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

const int N = 25, INF = 0x3f3f3f3f;

int n, m;
int minv[N], mins[N];
int R[N], H[N];
int ans = INF;

void dfs(int u, int v, int s)
{
    if (v + minv[u] > n) // 体积不够剪枝
        return;
    if (s + mins[u] >= ans) // 得不到更好的结果剪枝
        return;
    if (s + 2 * (n - v) / R[u + 1] >= ans) // 体积和表面积的关系 数学剪枝
        return;

    if (!u)
    {
        if (v == n)
            ans = s;
        return;
    }

    for (int r = min(R[u + 1] - 1, (int)sqrt(n - v)); r >= u; r--) // 限制关系剪枝
    {
        for (int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; h--)
        {
            int t = 0;
            if (u == m)
                t = r * r;
            R[u] = r, H[u] = h;
            dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
        }
    }
}
int main()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        minv[i] = minv[i - 1] + i * i * i;
        mins[i] = mins[i - 1] + 2 * i * i;
    }

    R[m + 1] = H[m + 1] = INF;
    dfs(m, 0, 0);

    if (ans == INF)
        ans = 0;

    cout << ans << endl;

    return 0;
}

《新程序员》：云原生和全面数字化实践

50位技术专家共同创作，文字、视频、音频交互阅读