算法-（DFS + 剪枝）【洛谷P1731】 [NOI1999] 生日蛋糕

题目链接

点此快速前往

题目总分析

就和我说的一样，这道题就是DFS加剪枝，非常好的一道题

我起初看到这个题我根本不知道怎么dfs才是正确的， 感觉变量有这么多不确定的，每一层的半径，每一层的高度，而且这之间的联系在刚看到这个题的我看来十分的小，应该是我太菜了导致的

深入往下看，你就发现实际上这道题已经告诉了你每一层的限制了，并不是完全无从下手，至少你知道这一层的半径和高度一定小于等于它底下那一层的半径和高度-1，所以我们不难想象出dfs的做法：最下面那一层的半径最大值是假设只有一层，n-1就是它起初的最大值，那么最小值就是总共的层数，，因为每一层都要至少要少1，所以最大的那一层半径和高度肯定就最小值就是层数

为什么不遍历高度而是半径呢？

你稍微列一下式子你就会发现，实际上半径对总面积的影响程度要高于高度的，所以想要最小，一定是从半径入手。

$$总体积n=\sum _{i=1}^m{R}_i\ast H_i$$

$$总面积m=R_0^2+\sum _{i=1}^m{R}_i^2\ast H_i$$

为什么总面积前面有个$R_0^2$

简单想想，虽然是每个圆柱都被另一个比它小的圆柱盖住了一个圆的面积，但是你从这个蛋糕的最上面去看，就不难发现，最上面的面积和其实就是最底层圆柱的顶面面积。

看到这可能已经想要去写了，不过先停一下
这道题dfs搜索只是第一步，而更重要的是剪枝，由于处理数据的量也是非常大的，如果不进行一些优化就没办法顺利进行

首先既然我们知道每一层最小的半径和高，那么我们就不难算出来到每一层为止，最小的体积和最小的面积分别是多少

有了上述的信息之后，我们在准备遍历之前可以先判断一下

1. 如果此时此刻接下来几层的最小面积加上此时的面积已经大于等于当前的最优解你，那就没有必要去遍历了。
2. 同样，接下里几层的最小体积加上此时的体积已经大于要求的总体积n，那么也没必要去遍历了
3. 这个是比较难想的，我们是从最下层遍历到最上层的，也就是说假设此时此刻遍历的层数半径为r，包括这一层之前的总体积为v以及总面积是s ， 总共的蛋糕体积是n，那么如果$2\ast (n-v)/r>此时的最优解$，同样也没有遍历下去的必要了

前两个好理解,第三个是什么东西啊？
很好我开始看到的时候也非常困惑，接下来推导一下你就懂了

从m开始now是已经搭建好的层数了，now-1就是接下来之后的层

$$接下里的面积应该是\sum _{i=1}^{now-1}{R}_i^2\ast H_i$$
看一下我第三条公式，你可以清楚的发现，$R_i$全部都小于当前这一层的 r 所以，接下里的面积必然比$2\ast (n-v)/r$大，如果这个面积都大于等于最优解了，那么就不需要遍历了

接下来就是代码实现了，基本思路已经写完，代码中有不理解的部分可以评论区提问一下或者私信。

总代码

#include<bits/stdc++.h>
using namespace std;
const int N = 25 , INF = 0x3f3f3f3f;
int n,m;
int ans = INF;
int Mins[N] , Minv[N];
void dfs(int now,int r,int h,int s,int v)
{
	int MH = h;
	if(now == 0){
		if(v == n){
			ans = min(ans, s);
		}
		return ;
	}
	
	if(Mins[now-1] + s >= ans) return;
	if(Minv[now-1] + v > n) return;
	if(2 * (n - v) / r + s >= ans) return;
	
	for(int i=r-1;i>=now;i--){
		if(now == m) s = i * i;
		MH = min(h-1 , (n - Minv[now-1] - v) / i / i);
		for(int j = MH ; j >= now ; j--){
			dfs(now-1 , i , j , s + 2 * i * j , v + i * i * j);
		}
	}
}

int main()
{
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		Mins[i] = Mins[i-1] + i * i * 2;
		Minv[i] = Minv[i-1] + i * i * i;
	}
	dfs(m,n,n,0,0);
	if(ans == INF) cout << 0 << '\n';
	else cout << ans << '\n';
	return 0;
}