<—点个赞吧QwQ

宣传一下算法提高课整理

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

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

当 $i < M$ 时，要求 $R_i > R_{i+1}$ 且 $H_i > H_{i+1}$。

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

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

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

输入格式

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

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

输出格式

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

数据范围

$1 \\le N \\le 10000$,
$1 \\le M \\le 20$

输入样例：

100
2

输出样例：

68

1. 优化搜索顺序$~\color{green}✔$
   • 自底向上搜，从大到小枚举 $r,h$ ;
2. 排除等效冗余$~\color{red}✖$
   • 由于蛋糕的大小要求自底向上从大到小，所以没有等效冗余
3. 可行性剪枝$~\color{green}✔$
   • $v+minv (u) \le n$
   • $u \le R_u \le min \{R_{u+1}-1,\sqrt {n-v}\}$
   • $u \le H_u \le min \{H_{u+1}-1,\dfrac{n-v}{r^2}\}$
4. 最优性剪枝$~\color{green}✔$
   若满足以下两点则剪枝
   • $s+mins (u) > ans$
   • $\dfrac{2*(n-v)}{R[u]}+s > ans$
     证明：
     $\begin{align} S_{1\sim u}=&\sum\limits_{k=1}^u{2 R_k H_k}\newline =&\dfrac{2}{R_{u+1}}\sum\limits_{k=1}^{u}R_k H_k R_{u+1}\newline >&\dfrac{2}{R_{u+1}}\sum\limits_{k=1}^{u}{R_k}^2 H_k\\\ =&\dfrac{2}{R_{u+1}}{(n-v)} \end{align} \\\ \therefore s + S_{1\sim u} = s + \dfrac{2}{R_{u+1}}{(n-v)} < ans $

代码

#include <iostream>
#include <cmath>
using namespace std;
const int N = 30,INF = 2e9;
int n,m;
int ans = INF;
int minv[N],mins[N];
int H[N],R[N];
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;
            H[u] = h,R[u] = r;
            dfs (u - 1,v + h * r * r,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;
}