UVA11196 Birthday Cake

· · 题解

根据题目给出的条件，确定下来这道题是爆搜加剪枝。

同时此题为 P1731 [NOI1999] 生日蛋糕 的强化版。

似乎在 剪贴板 里排版会更好。

基本公式

注意，从这里开始，所有公式将忽略 \pi，因为可以抵消。

设最底层为第 m 层，第 i 层的高度为 H_i，半径为 R_i ，则蛋糕表面积公式为：S_{1-m}=R_m\times R_m+∑^m_{i=1}2R_iH_i。

同时体积公式为：V_{1-m}=∑^{m}_{i=1}R_i^2\times H_i

图示

这个图对理解下列公式有帮助。

剪枝优化

1.优化搜索顺序

  1. 层间：从底部向上枚举。
  2. 层内：先枚举半径再枚举高（半径相对于高来说对体积的影响较大），半径由大到小，高度由大到小。

2.可行性剪枝

考虑第 u 层的 R_i 与 H_i 的值域

设总体积为 n，当前在第 u 层，第 u 层的高度为 H_u，半径为 R_u，体积为 V_u，搜索的时候第 m 层到第 u 层体积的累计值为 V，搜索的时候第 m 层到第 u 层面积的累计值为 S，当前搜索到的最小面积值为 S_{res}。

我们考虑第 u 层的 R_i 与 H_i 的值域。

根据图示，第 u 层的体积为总体积减去上下两部分体积之和。

则 n-V-\min\{∑^{u-1}_{i=1}V_i\}\geq R_u^2H_u，其中可以算出 \min\{∑^{u-1}_{i=1}V_i\} 的值，因为第 i 层的最坏情况就是半径和高度都为 i，且 H_u 最坏情况就是 u。

故公式可以化为 n-V-\min\{∑^{u-1}_{i=1}V_i\}\geq R_u^2 u，其中 n,V,u 都知道，则可以算出 R_u 的范围！

R_u\leq \min\{\sqrt{\dfrac{n-V-\min\{∑^{u-1}_{i=1}V_i\}}{u}},R_{u+1}-1\ \}

在代码中，此时 R_u 已经进行枚举弄出一个具体的值了，故 H_u 的范围也呼之欲出：

H_u\leq \min\{\dfrac{n-V-\min\{∑^{u-1}_{i=1}V_i\}}{R_u^2},H_{u+1}-1\ \}

当然，还要剪枝。

考虑表面积公式和体积公式之间的关系

S_{1-u}=∑^u_{i=1}2R_iH_i=2∑^u_{i=1}R_iH_i=\dfrac{2}{R_{u+1}}∑^u_{i=1}R_iH_iR_{u+1}>\dfrac{2}{R_{u+1}}∑^u_{i=1}R_i^2H_i V_{1-u}=n-V=∑^u_{i=1}R_i^2H_i

将 V_{1-u} 带入 S_{1-u} 中，可得 S_{1-u}>\dfrac{2}{R_{u+1}}(n-V)，又因为 S_{1-m}=S+S_{1-u}\geq S_{res}，故 S+\dfrac{2}{R_{u+1}}(n-V)\geq S_{res} 就可以剪枝掉。

3.最优性剪枝

如果当前的累计值加上之后的最小值大于等于目标值，则可以剪枝。

放到代码中，就是当前的体积加上之后的最小体积还大于 n，则剪枝。

至此，所有剪枝就讲完了，码代码应该不是什么大问题。

代码

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

const int N = 25;
int n, m;
int minv[N], mins[N], R[N], H[N];
int res = 1e9;

void dfs(int u, int v, int s) {
    if (v + minv[u] > n) return;
    if (s + mins[u] >= res) return;
    if (s + 2 * (n - v) / R[u + 1] >= res) return;
    if (u == 0) {
        if (v == n) res = min(res, s);
        return;
    }
    for (int r = min(R[u + 1] - 1, (int)sqrt((n - v - minv[u - 1]) / u)); r >= u; r--) {
        for (int h = min(H[u + 1] - 1, (n - v - minv[u - 1]) / r / r); h >= u; h--) {
            H[u] = h, R[u] = r;
            int t = u == m ? r * r : 0;
            dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
        }
    }
}

int cas; 

int main() {
    while (cin >> n >> m) {
        cas++;
        res = 1e9;
        if (n == 0) break;
        memset(minv, 0, sizeof minv);
        memset(mins, 0, sizeof mins);
        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] = 2e9;
        dfs(m, 0, 0);
        cout << "Case " << cas << ": " << ((res == 1e9) ? 0 : res) << endl;
    }

}
//此代码成功拿到uva11196最优解！