P1731 生日蛋糕

题面

题目背景

数据加强版 link

题目描述

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

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

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

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

100
2

样例输出 #1

68

思路

主要是说说剪枝的思路：

1.搜索顺序：

从底下往上面搜一定是好的，因为底下的半径是最大的，高度也是最高的，所以给上面留的体积就不多了，这样可以减少搜索的分支数量。

根据面积公式 $V = \pi r^2\times{h}$ 所以先枚举半径，后枚举高度，同样，从大到小枚举。

注：由于题面不要求 $\pi$ 的计算，所以一下省略。

那么就要看一下 $r$ 和 $h$ 的范围了：

首先假设现在看到了从上到下数第 $u$ 层（从下到上遍历），设这个时候它下面的蛋糕体积是 $v$，由于它上面的蛋糕还有第 $u-1,u-2,u-3,u-4,\dots,2,1$ 层等等，而且高度和半径都是从上到下严格单调递增的，所以 $r\ge u,h \ge u$ ，再来看上界，它肯定比已经看过的第 $u+1$ 层要小 1，所以 $r \le r_{u + 1} - 1,h \le h_{u + 1} - 1$。

仅仅这样吗？ 不是。

$n - v \ge r^2h$

$h$ 最小取 $u$ ，所以 $r \le \sqrt{\frac{n-v}{u}}$，由于先枚举的 $r$，所以 $h\le\frac{n-v}{r^2}$。

所以取个 min 就是：

$\begin{cases} u\le r \le \min(r_{u + 1} - 1,\sqrt{\frac{n-v}{u}}) \\ u\le h \le \min(h_{u + 1} - 1, \dfrac{n-v}{r^2}) \end{cases}$

2.可行性剪枝

如果 $v + minv_{u} > n$，其中 $minv_u$ 为从上到下前 $u$ 层的体积最小值，那么这个方案就没有必要继续向上搜了，因为一定不满足。

3.最优性剪枝

如果 $s + mins_u\ge{ans}$ ，（其中 $s$ 代表下面已经搜过的面积，与 $v$ 定义类似）那么也没有必要往下搜了，因为当前已经覆盖的面积加上继续想上搜，即使上面是最理想的情况，也无法更新答案，所以没有搜的必要。

$\text{Last but not least}$，还有最后一点小剪枝（数学推导）：

$S_{1\sim u}=\sum^u_{k=1}2r_kh_k=\frac2{r_{u+1}}\sum^u_{k=1}r_kh_kr_{u+1}\ge\frac2{r_{u+1}}\sum^u_{k=1}r_k^2h_k$

（为什么能取等？当搜完所有层的时候，两边都是零。）

而：

$n-v=\sum^u_{k=1}r_k^2h_k$

\begin{gather} \therefore S_{1\sim u}\ge\frac{2(n-v)}{r_{u+1}}\\ \because s + S_{1\sim u} <{ans}\\ \therefore s + \frac{2(n-v)}{r_{u+1}} < ans \end{gather}

也就是说，$s + \frac{2(n-v)}{r_{u+1}} \ge ans$ 的时候，也没必要接着往下搜了。

剪枝——完结撒花！

代码

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

// 自底向上走，给未来留的余地越少越好
// 先枚举半径，再枚举高，从大到小枚举，同样的道理
// 当前枚举的是第 u 层(从上往下)，那么半径大于等于 u，小于等于下一层的半径-1
// 体积：u 以下体积为 v，n - v >= r^2h, h 最小取1(u ?)，所以 r <= \sqrt(n-v) ( < ?)
// u <= r(u) <= min(r(u + 1) - 1, \sqrt(n-v))
// u <= h <= min(h(u + 1) - 1, (n - v) / r^2)
// 预处理下前 u 层的体积最小值，看它加上v是否　<= n
// 预处理前 u 层表面积最小值，看它加当前的表面积是否 < ans，因为无法更新答案就没必要接着搜了
// 用当前体积估算上面的表面积，若不能更新也没必要接着搜了

const int N = 25;

int n, m;
int minv[N], mins[N]; //前若干层的面积/体积最小值
int R[N], H[N];
int ans = 0x3f3f3f3f;

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) / u)); 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] + i * i * 2;
    }
    R[m + 1] = H[m + 1] = 0x3f3f3f3f; //让最后一层最大值没有什么限制
    DFS(m, 0, 0); //从第 m 层开始， 体积和面积都是0
    cout << ((ans == 0x3f3f3f3f)? 0: ans) << endl;
    return 0;
}