[数据结构与算法]2021.8.6 [NOI1999] 生日蛋糕：一道剪枝复杂的深搜

题目：P1731 [NOI1999] 生日蛋糕 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这是一道深搜剪枝的好题。为什么好呢？..

因为我调试的快吐了，好多剪枝条件，一直没有想到...头秃= =

以前没有遇到过这么多剪枝条件的题目...

刚开始这道题开住我，因为这道题与一般的深搜题不一样，没有什么明显的选择条件。仔细读题，要求R、H递增，那么R、H的边界条件我们就可以找出，两个for循环列出R、H的枚举，每次枚举的R、H进入下一层搜索。这是本题与一般深搜题相比不同寻常的一点。

for (int R = r-1; R >= m; R--)//枚举这一层的半径
	{			
		if (m == M)//处理最底层蛋糕的上表面
				area = R * R;
		int Hmax = min(int((rest - MinV[m - 1]) / (R * R)),h-1);//相当于对H剪枝
		for (int H = Hmax; H >= m; H--)//枚举这一层的高度
		{
			//cout << "r=" << R << "h=" << H << "area=" << area + 2 * R * H << "rest=" << rest - R * R * H << "m=" << m << endl;//测试
			dfs(R, H, area + 2 * R * H, rest - R * R * H, m - 1);//进入下一层
		}
	}

对下面代码中剪枝条件3：一个关键推理进行说明。(太懒了，手写的将就着看吧，反正只有我自己看)

#include<bits/stdc++.h>
using namespace std;
int N, M, ans = 1e9;
int MinS[20], MinV[20];
void dfs(int r, int h, int area, int rest, int m)//r当前层数半径 h当前层数高 area当前层数表面积 rest当前层数剩余可用体积 m当前层数(可以理解为初到当前层)
{
	if (m == 0 && rest == 0)
	{
		ans = min(ans, area);//标准深搜最小值
		return;
	}
	/**玛德下面把m写成M一下午没有找出来错误！！！气死我了！！！**/
	if (area + MinS[m - 1] >= ans) return;//剪枝条件1：当前表面积 + 剩余最小表面积之和应该 < ans
	if (rest < MinV[m - 1] || m <= 0)return;//剪枝条件2：剩余可用体积应该 >= 剩下最小体积
	if (area + 2 * rest / r >= ans) return;//剪枝条件3：一个关键推理
	int Rmax = min(int(pow(rest - MinV[m - 1], 0.5)),r-1);//假设H==1,取R的最大值,相当于对R剪枝
	for (int R = r-1; R >= m; R--)//枚举这一层的半径
	{			
		if (m == M)//处理最底层蛋糕的上表面
				area = R * R;
		int Hmax = min(int((rest - MinV[m - 1]) / (R * R)),h-1);//相当于对H剪枝
		for (int H = Hmax; H >= m; H--)//枚举这一层的高度
		{
			//cout << "r=" << R << "h=" << H << "area=" << area + 2 * R * H << "rest=" << rest - R * R * H << "m=" << m << endl;//测试
			dfs(R, H, area + 2 * R * H, rest - R * R * H, m - 1);//进入下一层
		}
	}
}
int main(void)
{
	int sum = 0;
	cin >> N >> M;//N为蛋糕体积，M为蛋糕层数
	for (int i = M; i >= 1; i--)
	{
		sum += i * i * i;
	}
	if (sum > N)
	{
		cout << 0;//先将无解的情况排除
		return 0;
	}
	for (int i = 1; i <= M; i++)
	{
		MinV[i] = MinV[i - 1] + i * i * i;//从上往下数，前i层最小体积之和
		MinS[i] = MinS[i - 1] + 2 * i * i;//从上往下数，前i层最小表面积之和
	}
	dfs(N, N, 0, N, M);
	if (ans < 1e9)
	{
		cout << ans;
	}
	else
		cout << 0;
	return 0;
}

这道题花了我好长好长时间。我太菜了呀...