P1731 [NOI1999] 生日蛋糕 题解

发表于 更新于

题目链接·洛谷 (QwQ,对不起，把题讲难了)

针对搜素传参和剪枝的练习和题解

前言

  当我们做一道题的时候首先要认真读题是吧 （该不会有不是的吧QwQ

  首先让我们看看这道题的题面：

题面

题目描述

7 月 17 日是 Mr.W 的生日，ACM-THU 为此要制作一个体积为 \(N\pi\) 的 \(M\) 层生日蛋糕，每层都是一个圆柱体。

设从下往上数第 \(i\)（\(1 \leq i \leq M\)）层蛋糕是半径为 \(R_i\)，高度为 \(H_i\) 的圆柱。当 \(i \lt M\) 时，要求 \(R_i \gt R_{i+1}\) 且 \(H_i \gt H_{i+1}\)。

由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积 \(Q\) 最小。

请编程对给出的 \(N\) 和 \(M\)，找出蛋糕的制作方案（适当的 \(R_i\) 和 \(H_i\) 的值），使 \(S=\dfrac{Q}{\pi}\) 最小。

（除 \(Q\) 外，以上所有数据皆为正整数）

输入：

  第一行为一个整数 \(N\)（\(N \leq 2 \times 10^4\)），表示待制作的蛋糕的体积为 \(N\pi\)。

第二行为 \(M\)（\(M \leq 15\)），表示蛋糕的层数为 \(M\)。

输出：输出一个整数 \(S\)，若无解，输出 \(0\)。

样例

1
2
100
2
1
68

  根据之前的文章中提到的寻找的参数的方式，让我们来找一下:

  那么我们能很轻松的找到如下

  \(层数(X)，上一层的半径(R)，上一层高度(H)，现在的总面积(S)，剩余的体积(V)\)这几个参数；这些就够了。让我们边做边练。

  刚开始做的时候，我们在写\(DFS\)的时候发现，我们应该传一个什么样的初值进去呢(自下而上的(物理上的))？？？ (\(ps:\)你要自上而下，那么你的枚举下届是什么呢？？？)

  so,让我们再看题目(仔细琢磨) 题目中说每一层的的\(H\)和\(R\)都比下层（物理上的）要小的 || 而且 || 他还对层数进行了要求。

  🧐也就是说再应该有层数的地方\(H\)和\(R\) 应该 $ ≧ 1$ (要是为零的不就是不存在嘛QwQ那么就无法满足层数了) 于是乎，我们应该再每层都为上层而考虑，而且又要考虑最小的话，那么我们只要让每一层差值都为一，到最顶层刚好停止就行了。

  我们可得 \[每层的高度(H)和半径(R)最小为层数(X)\]   由上则有体积的最小范围（后面剪枝会用到的 \[每层最小体积为层数(X)的三次方(r^{2} \times h = X \times X \times X = X^3)\] 由上我们就能写出代码了 

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int min_V[100000],minn=0x7fffffff;
int n,m;
//层数，上一层的半径，上一层高度，现在的总面积，剩余的体积
inline void dfs(int X,int R,int H,int S,int V){
	if (V<0)return ;
	if (X<0)return ;	
	if (X==0){
		if (V==0){
            if(S>minn)
                minn=S;
            }
		return;
	}
	for(register int i=R-1;i>=X;i--){//;枚举下一层半径
		for(register int j=H-1;j>=X;j--){//枚举下一次高度
			if (X==m){S=i*i;}
			dfs(X-1,i,j,S+2*j*i,V-i*i*j);
		}
	}
}
int main() {
//	freopen("in.txt","r",stdin);
	scanf("%d%d",&n,&m);
	dfs(m,(int)sqrt(n/m),n/(m*m),0,n);
	if (minn==0x7fffffff){printf("-1\n");return 0;}
	printf("%d\n",minn);
    return 0;
}

ヾ(≧▽≦*)o,好耶，为能能看到这里的鼓掌。 但是，到这里也还是不能全A的，我们再之上要进行剪枝&优化

      `for(register int i=1;i<=m;i++){min_V[i]=i*i*i;}`

[^1]

      `if (V-i*i*j<min_V[X-1]){continue;}`

[^2]

      `if (S+2*j*i>=minn){continue;}`

[^3]

      `if (S+2*(V-i*i*j)/(i)>minn)continue;`

[^4]

以上剪枝是什么意思呢，emmm……先自己思考3分钟；(其实我这里为了提速把他放在for循环里了比较，可能看的不是很使用可以把他翻译汉字更好理解)

ok，开始讲解： [^1] : 预处理出每一层最小体积

[^2] : 如果下一层的题解小于最小体积,不合法，返回

[^3] : 如果下一次出来的表面积大于最小值，就算不是最后一层那也不用递归了，因为最后的结构一定大于历史最小值（还要可以把前面的判断if(S>minn)省略掉了,没有必要了）

[^4] : 这个2*(V-i*i*j)/(i)是通过公式推出本层的侧面积，但是用的下一层的半径和高度，所以回更小，如果这个剪枝就是很玄学啊,剪得是最底一层(也就是本层)的表面，到后面貌似没有什么用（我写到这里才发现，但是不加就过不了QwQ，如有大佬，请到这里） 公式如下

\[\begin{align*} \\2 R \times H = C_侧面积① \\R^2 \times H =V_当前层② \end{align*}\] 然后又②可得\[H= \frac{V}{R^2} ③\]

2VR=C侧面积

于是就有了以上代码…… 就先到此执笔，等有人催更了我再补……咕咕咕

🍂全文完ヾ(≧▽≦*)o↩︎