• 制作一个体积为NπN\pi,共MM层的蛋糕
  • 从上往下数第i,(1iM)i,(1\leq i\leq M)的蛋糕是半径为RiR_i,高度为HiH_i的圆柱
  • i<Mi<M时,要求Ri>Ri+1R_i>R_{i+1}Hi>Hi+1H_i>H_{i+1}
  • 使得蛋糕的表面积最小

在这里本题需要输出的答案并不是最小的表面积,而是最小表面积除以π\pi之后的结果

思路

  • 深搜
    • 模拟拼蛋糕
    • 暴力枚举下一层可能的蛋糕半径与高度
    • 只需记录更新侧面积,所有顶面积等于最底层蛋糕的底面积
  • 超时?
    • 剪枝!!!

如何剪枝

在这里分可行性剪枝与最优性剪枝

最优性剪枝

  1. 当前已拼成的蛋糕表面积比已经记录的最优解大

可行性剪枝

  1. 无可用体积
  2. 拼成这些层最少体积大于当前需要拼的体积
  3. 目前枚举的高度半径不足以拼完蛋糕
  4. 当前可能拼成的最大体积比需要拼的体积少

代码

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;
int n, m;
int minArea = 1 << 30;//记录最优解
int area = 0;//记录当前解
int minV[30], minA[30];//分别记录拼成i层最小可能的体积和表面积
int MaxVforNRH (int n, int r, int h) {
int v;
for (int i = 0; i < n; ++i) v += (r - i) * (r - i) * (h - i);
return v;
}//计算在还有n层没拼完,当前一层的半径为r,高度为h时可能拼成的最大体积
void dfs (int v, int n, int r, int h) {
if (n == 0) {
if (v) return;
else {
minArea = min(minArea, area);
return;
}
}
if (v <= 0) return;//可行1
if (minV[n] > v) return;//可行2
if (area + minA[n] >= minArea) return;//最优
if (h < n || r < n) return;//可行3
if (MaxVforNRH(n, r, h) < v) return;//可行4
for (int rr = r; rr >= n; --rr) {//爆搜
if (n == m) area = rr * rr;
for (int hh = h; hh >= n; hh--) {
area += 2 * rr * hh;
dfs (v - rr * rr * hh, n - 1, rr - 1, hh - 1);
area -= 2 * rr * hh;
}
}
}
int main () {
cin >> n >> m;
minA[0] = 0;
minV[0] = 0;
for (int i = 1; i <= m; ++i) {
minV[i] = minV[i - 1] + i * i * i;
minA[i] = minA[i - 1] + 2 * i * i;
}
if (minV[m] > n) cout << 0 << endl;
else {//处理搜索边界
int maxH = (n - minV[m - 1]) / (m * m) + 1;
int maxR = sqrt(double(n - minV[m - 1]) / m) + 1;
area = 0;
minArea = 1 << 30;
dfs (n, m, maxR, maxH);
if (minArea == 1 << 30) cout << 0 << endl;
else cout << minArea << endl;
}
return 0;
}