P1731. 生日蛋糕

发表于 分类于 阅读次数： Waline： 本文字数： 1k 阅读时长 ≈ 3 分钟

考点

  • DFS
  • 剪枝

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 50, inf = 0x3f3f3f3f;
ll ans = inf, n, s, v, m, minv[maxn], mins[maxn];
int r[maxn], h[maxn];

void dfs(int now) {
  if (!now) {
    if (v == n) ans = min(ans, s);
    return;
  }
  for (r[now] = min((int)sqrt(((double)n - v) / now), r[now + 1] - 1);
       r[now] >= now; --r[now]) {
    for (h[now] = min((int)((double)(n - v) / r[now] / r[now]), h[now + 1] - 1);
         h[now] >= now; --h[now]) {
      ll tmpv = r[now] * r[now] * h[now], tmps = 2 * r[now] * h[now];
      if (v + tmpv + minv[now - 1] > n) continue;
      if (s + tmps + mins[now - 1] > ans) continue;
      if (s + (double)2 * (n - v) / r[now] > ans) continue;
      if (now == m) s += r[now] * r[now];
      s += tmps, v += tmpv;
      dfs(now - 1);
      s -= tmps, v -= tmpv;
      if (now == m) s -= r[now] * r[now];
    }
  }
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    mins[i] = mins[i - 1] + 2 * i * i;
    minv[i] = minv[i - 1] + i * i * i;
  }
  r[m + 1] = h[m + 1] = inf;
  dfs(m);
  ans == inf ? cout << -1 : cout << ans;
  return 0;
}

思路

上面题解是拿加强版做的，本题数据很烂

根据题意，第1层是最小的，第m层是最大的

从小到大，单独每个圆柱体的上表面积等于s1、s2、s3;

按照题意累堆在一起，那么总上表面积等于s1 + (s2 - s1) + (s3 - s2) = s3

所以处理第m层时，就可以直接加上总上表面积，只需要考虑每个部分的侧面积处理

根据题意，r[k]代表第k层的半径，h[k]代表第k层的高度，那么有：

  • r[0] = h[0] = 0, r[m + 1] = h[m + 1] = inf
  • r[1] < r[2] < r[3] < ... < r[m]
  • h[1] < h[2] < h[3] < ... < h[m]
  • r[k] >= k, h[k] >= k
  • 第k层的最小侧面积等于2 * k * k，第k层的最小体积等于k * k * k

可以用mins[k]、minv[k]预先打表1 ~ k层的最小侧面积、最小体积的前缀和

接下来到各种恶心的剪枝环节：

假设当前层数为now，now + 1 ~ m的体积和为v，now + 1 ~ m的侧面积和为s

搜索顺序

从第m层倒序搜索至第1层，r和h也从大到小遍历，必须记住的剪枝技巧！

逻辑上理解，先固定大的，小的可能性搜索树自然就会少。

r和h的取值范围

根据公式： \[ r^2h=\left( n-v \right) \Longrightarrow r=\sqrt{\frac{\left( n-v \right)}{h}} \] 而第now层的h最小值为now，那么r的最大值为：

1
sqrt(((double)n - v) / now)

注意！除法操作时先转换成double，避免精度缺失导致WA

又因为当前的半径肯定要比上一层的小，所以还有一个最大值备选项：

1
r[now + 1] - 1

所以最终r的取值范围：

1
2
for (r[now] = min((int)sqrt(((double)n - v) / now), r[now + 1] - 1);
       r[now] >= now; --r[now])

h同理得到

1
2
for (h[now] = min((int)((double)(n - v) / r[now] / r[now]), h[now + 1] - 1);
     h[now] >= now; --h[now])

卡常与可行性剪枝

1 ~ now的最小体积加上v一定小于等于n，不然就没有意义了，按道理应该这么写：

1
if (v + minv[now] > n) continue;

上述写法会把now的改变留到下一次递归判断，正常的DFS也确实是这么标准的模板——

但无疑这样会增加多余的栈开销，本题也会TLE，遂改成：

1
2
ll tmpv = r[now] * r[now] * h[now];
if (v + tmpv + minv[now - 1] > n) continue;

最优性剪枝

1 ~ now的最小侧面积加上s一定小于等于ans，不然没必要继续搜下去，所以有：

1
2
ll tmps = 2 * r[now] * h[now];
if (s + tmps + mins[now - 1] > ans) continue;

我们的r和h都是利用n - v来剪枝的，尝试利用不等式放缩来剪枝，1 ~ now的最小侧面积和有不等式： \[ 2\sum{\begin{array}{c} now\\ k=1\\ \end{array}}r\left[ k \right] \cdot h\left[ k \right] =\frac{2}{r\left[ now \right]}\sum{\begin{array}{c} now\\ k=1\\ \end{array}}r\left[ k \right] \cdot h\left[ k \right] \cdot r\left[ now \right] \geqslant \frac{2}{r\left[ now \right]}\sum{\begin{array}{c} now\\ k=1\\ \end{array}}r\left[ k \right] ^2\cdot h\left[ k \right] =\frac{2}{r\left[ now \right]}\cdot \left( n-v \right) \] 也就是说，1 ~ now的侧面积和最小值为\(\frac{2\left( n-v \right)}{r\left[ now \right]}\)，可以得到：

1
if (s + (double)2 * (n - v) / r[now] > ans) continue;