生日蛋糕

题目

P1731 [NOI1999] 生日蛋糕 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 168. 生日蛋糕 - AcWing题库

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

设从下往上数第 $i$（$1\le i\le M$）层蛋糕是半径为 $R_i$，高度为 $H_i$ 的圆柱。当 $i<M$ 时，要求 $R_i>R_{i+1}$ 且 $H_i>H_{i+1}$。

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

请编程对给出的 $N$ 和 $M$，找出蛋糕的制作方案（适当的 $R_i$ 和 $H_i$ 的值），使 $S=\frac{Q}{\pi }$ 最小。

（除 $Q$ 外，以上所有数据皆为正整数）

输入格式

第一行为一个整数 $N$（$N\le 2\times 10^4$），表示待制作的蛋糕的体积为 $N\pi$。

第二行为 $M$（$M\le 15$），表示蛋糕的层数为 $M$。

输出格式

输出一个整数 $S$，若无解，输出 $0$。

样例 #1

样例输入 #1

100
2

样例输出 #1

68

思路

设每一层的半径为 $R_i$, 高度为 $H_i$。 要求的外表面积包含顶部面积$S_{top}$, 和柱面$S_{col}$ , 其各自的值为： $S_{top}=R_m^2\times \pi$ $S_{col}=2\pi R_m{H}_m+2\pi R_{m-1}{H}_{m-1}+...+2\pi R_1{H}_1$ 最终表面积就等于他俩之和 $Q=S_{top}+S_{col}$

因为最后求的是 $\frac{Q}{\pi }$, 故这里可以把$\pi$ 都省去。

搜索顺序：从底层m往上搜, 当前层数为u, 已用体积为v, 当前表面积为s 每层枚举$R,H$的可能值。

剪枝优化：

1. $R,H$的范围： $u\le R_u\le \min \{R_{u+1}-1,\sqrt{n-v}\}$ $u\le H_u\le \min \{H_{u+1}-1,\frac{n-v}{R_u^2}\}$ 题目要求为正整数, 且低下比上面高, 故当前的$R,H$最低都为$u$, 即当前层数。 最大肯定要小于下面一层的高度, 即 小于$R_{u+1},H_{u+1}$ , 且体积不能超过$n$, 又$n-v>=\pi R_u^2{H}_u$ , $H$ 最小取1, 故 $R_u\le \sqrt{n-v}$ 。而 $H_u\le \frac{n-v}{R^2}$
2. 计算出表面积和体积的每层最小值： $minv(u)+v\le n$ $mins(u)+s\le ans$
3. 将体积公式和柱体表面积公式对比： $S_{1\sim u}={\sum }_{k=1}^{u}2\pi R_k{H}_k=\frac{2\pi }{R_{u+1}}{\sum }_{k=1}^u{R}_k{H}_k{R}_{u+1}\ge \frac{2\pi }{R_{u+1}}{\sum }_{k=1}^u{R}_k^2{H}_k$ (等号在$R_{u+1}=0$时成立) $n-v=\pi {\sum }_{k=1}^u{R}_k^2{H}_k$
   因为$R_{u+1}>R_k$, 故 $R_k{R}_{u+1}>R_k^2$ , 可得$S_{1\sim u}\ge \frac{2}{R_{u+1}}(n-v)$ 可得到一个优化式：$ans\le s+\frac{2(u-v)}{R_{u+1}}$ 时, 方案不成立, 可以直接回溯

令人唏嘘的是, 这个代码还是过不了洛谷的10w数据加强版, 也没找到更好的优化方法。

代码

const int N = 16, INF = 0x3f3f3f3f;
 
int minv[N], mins[N];
int R[N], H[N];
int n, m;
int ans = INF;
 
void dfs(int u, int s, int v)
{
    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 i = min(R[u + 1] - 1, (int)sqrt(n - v)); i >= u; i--)
        for (int j = min(H[u + 1] - 1, (n - v) / (i * i)); j >= u; j--)
        {
            int t = 0;
            if (u == m)
                t = i * i; // 整个上表面的面积
            R[u] = i, H[u] = j;
            dfs(u - 1, s + 2 * i * j + t, v + i * i * j);
        }
}
 
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    { // H最小为1
        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 / 2)
        ans = 0; // 无解
    cout << ans << endl;
    return 0;
}