题目做法

思路

这道题使用的是 DFS(深搜)：

  • 我们可以从下向上进行搜索，同时记录上一次搜索的 $h$（高度） 和 $r$（半径）。

  • 当我们搜索到最上面一层了之后，就判断答案是否合法，如果合法就保存最小值。

  • 于是我们就有一个最基础的搜索思路

  • 我们可以写一个DFS函数传入五个变量，$(x, s, v, last_h, last_r)$ 分别表示我们当前搜索的蛋糕层数，已经使用的表面积，已经使用的体积，上一层的高度，上一层的半径

  • 显然它有着一个及其庞大的决策库，我们直接搜索是会 $TLE$ 的

剪枝

  • 可行性剪枝：如果沿着当前思路永远做不出满足条件的蛋糕呢？
  • 最优化剪枝：如果沿着当前思路蛋糕一定不比我们之前做出来的表面积更小呢？

所以可以总结为：
① 要是剩下体积除以最大(虽然取不到)半径所得到的表面积+累计表面积大于答案，就 $return$

② 要是剩下来的体积已经小于该层最小体积了就 $return$

③ 还有为了剪枝,我们要起先预处理某一层的最大不可的表面积和体积

标程讲解

略写

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
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

#define int long long

int ans = 0x7777777f;
int n, m;
int min_v[20005], min_s[20005];

void dfs(int x, int s, int v, int last_h, int last_r)
{
	if (!x)//已经到了第一层 
	{
		if (v == n) ans = min({ans, s});//判断是否为合法答案 
		return;
	}

	if (s + 2 * (n - v) / last_r > ans) return;//要是剩下体积除以最大(虽然取不到)半径所得到的表面积+累计表面积大于答案
	if (v + min_v[x] > n) return;//要是剩下来的体积已经小于该层最小体积了
	if (s + min_s[x] > ans) return;//要是最小面积+当前累计表面积已经比已知答案大了
	for (int i = last_r - 1; i >= x; i--)//从大到小枚举该层半径
	{
		if (x == m) s = i * i;//要是现在是第一层那么就直接加上最小表面积
		int max_h = min({last_h - 1, (n - v - min_v[x - 1]) / (i * i)});
		for (int j = max_h; j >= x; j--)//从大到小枚举该层高度
			dfs(x - 1, s + 2 * i * j, v + i * i * j, j, i);
	}
}
signed main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		min_v[i] = min_v[i - 1] + i * i * i;
		min_s[i] = min_s[i - 1] + 2 * i * i;
	}

	int max_r = sqrt(n);
	dfs(m, 0, 0, n, max_r);

	cout << (ans == 0x7777777f ? 0 : ans);

	return 0;
}

详解

  • int ans = 0x7777777f; 是一个变量声明，它定义了一个名为ans的整数变量，并把它初始化为十六进制数0x7777777f，这个数很大，相当于十进制数2004318079。

  • int n, m; 是另外两个变量声明，它定义了两个名为n和m的整数变量，分别表示蛋糕的体积和层数。

  • int min_v[20005], min_s[20005]; 是两个数组声明，它定义了两个大小为20005的整数数组min_v和min_s，分别表示每一层蛋糕最小可能占用的体积和表面积。

  • void dfs(int x, int s, int v, int last_h, int last_r) 是一个函数定义，它定义了一个名为dfs的函数，它没有返回值（void），并接受五个整数参数：x表示当前处理的层号，s表示当前已经使用的表面积，v表示当前已经使用的体积，last_h表示上一层的高度，last_r表示上一层的半径。

  • if (!x) { if (v == n) ans = min({ans, s}); return; } 是一个条件语句，它判断x是否为零。如果是零，说明已经处理完所有层了。然后它再判断v是否等于n。如果是n，说明已经达到了目标体积。那么就用min函数比较ans和s的大小，并把较小的值赋给ans。最后用return语句结束函数。

  • if (s + 2 * (n - v) / last_r > ans) return; 是另一个条件语句，它用来剪枝优化搜索过程。它计算了当前表面积加上剩余体积所需的最小表面积（假设剩余部分是一个圆柱），并与ans比较。如果大于ans，说明这条搜索路径不可能得到更优解了，就可以直接返回。

  • if (v + min_v[x] > n) return; 是再一个条件语句，它也用来剪枝优化搜索过程。它计算了当前体积加上剩余层数所需的最小体积（假设每一层都是最小可能占用的体积），并与n比较。如果大于n，说明这条搜索路径不可能达到目标体积了，就可以直接返回。

  • if (s + min_s[x] > ans) return; 是最后一个条件语句，它同样用来剪枝优化搜索过程。它计算了当前表面积加上剩余层数所需的最小表面积（假设每一层都是最小可能占用的表面积），并与ans比较。如果大于ans，说明这条搜索路径不可能得到更优解了，就可以直接返回。

接下来是一个for循环，它用来遍历所有可能的高度和半径，并递归调用dfs函数。

  • for (int h = min(last_h - 1, (n - v) / (last_r * last_r)); h >= x; --h) 是一个for循环的第一部分，它定义了一个整数变量h，并给它赋了一个初始值。这个初始值是last_h - 1和(n - v) / (last_r * last_r)中较小的那个。这样做是为了保证当前层的高度不超过上一层的高度，并且不超过剩余体积所能容纳的最大高度。然后它定义了一个循环条件，即h必须大于等于x。这样做是为了保证每一层至少有x单位的高度。最后它定义了一个更新表达式，即每次循环结束后，h减一。这样做是为了遍历所有可能的高度。
  • for (int r = min(last_r - 1, int(sqrt((n - v) / h))); r >= x; --r) 是一个for循环的第二部分，它也定义了一个整数变量r，并给它赋了一个初始值。这个初始值是last_r - 1和int(sqrt((n - v) / h))中较小的那个。这样做是为了保证当前层的半径不超过上一层的半径，并且不超过剩余体积所能容纳的最大半径（假设当前层是圆柱）。然后它也定义了一个循环条件，即r必须大于等于x。这样做是为了保证每一层至少有x单位的半径。最后它也定义了一个更新表达式，即每次循环结束后，r减一。这样做是为了遍历所有可能的半径。
  • dfs(x - 1, s + 2 * r * h + (x == m ? r * r : 0), v + r * r * h, h, r); 是for循环内部执行的语句，它调用dfs函数并传入五个参数：x - 1表示处理下一层；s + 2 * r * h + (x == m ? r * r : 0)表示更新表面积（加上当前层侧面积和顶面积（如果是最外层））；v + r * r * h表示更新体积（加上当前层体积）；h表示传递当前层高度；r表示传递当前层半径。