由“生日蛋糕”这道题引出。

 

https://www.luogu.org/problemnew/show/P1731

先从题目中提取一些做题可能用得到的信息：

1.从上往下数第i层（i<M）的蛋糕的半径 R_i 总是比 R_i-1 小

2.实数计算与本题并没有关系

 

接下来考虑如何做题：

这道题可以用深度优先搜索做，但是为什么呢？

不妨先将题目中出现的各个表达式展开一下

蛋糕的体积为 Nπ ，从上往下数第 i 层的体积为 πr_i²h_i ， 则整个蛋糕的体积为 Σ^m_i=1   πr_i²h_i。

所以N就是去掉了π的Nπ啦

蛋糕的表面积就是 Σ^m_i=1   2πr_ih_{i ，}所以题目中的S就是去掉π的此式子

 

此时，可以看出，题目中的一个约束条件：体积Nπ    已经和答案S（乘以一个π）通过 每一层的h和r 链接起来了，

也就是说，当每一层的蛋糕体积加起来的和等于Nπ时，此时的表面积才有可能被接受成最优解。

然而，这个约束条件还不够劲，仔细读一下题目，发现：从上往下数第i层（i<M）的蛋糕的半径 R_i 总是比 R_i-1 小（就是往上数第十二句那一句），

发现这个约束条件真是太给力了，再加上M那较小的数据范围，似乎用搜索做就是顺理成章的事了，再加上一些剪枝，就可以通过本题了。

 

---

 

 

前面说了，此题目的计算都是在整数范围内的，这大概也是本题可以用搜索做的原因之一吧？

现在时间不多，马上放学，剩下的内容我会在明天补上。

先给出此题的代码：（见后文）

关于这份代码，放在这里的目的是想要说一下，如果将第16和第17行代码中的for语句改成这样：

for(int i = deep; i < r1; ++i)
        for(int j = deep; j < h1; ++j)

程序的效率将会大大降低，原本能通过的程序也会因为此“微不足道”的改动而惨惨TLE，这就涉及到搜索顺序对于程序效率的影响……推荐一篇能够用于参考的文档：《信息学竞赛中搜索问题的常见优化技巧重庆一中  黄晓愉》

（来自2006年全国信息学冬令营讲座）

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 int n,m,s;
 7 int minv[20];
 8 void dfs(int r1, int h1, int nwii, int ns, int deep) {
 9     if(ns >= s) return;
10     if(nwii == n && deep == 0) s = ns;
11     if(nwii >= n || deep == 0) return;
12     
13     if(2*(n-nwii)/r1 + ns >= s) return;
14     if(minv[deep] + nwii > n) return;
15     
16     for(int i = r1-1; i >= deep; --i)
17         for(int j = h1-1; j >= deep; --j) {
18             if(i*i*j + nwii > n) continue;
19             if(deep == m)
20             dfs(i, j, nwii + i*i*j, ns + 2*i*j + i*i, deep - 1);
21             else
22             dfs(i, j, nwii + i*i*j, ns + 2*i*j, deep - 1);
23         }
24 }
25 
26 int main() {
27     s = 200000000;
28     cin>>n>>m;
29     
30     for(int i = 1; i <= m; ++i) {
31         minv[i] = minv[i-1] + i*i*i;
32     }
33     dfs(28 ,28 , 0, 0, m);
34     if(s == 200000000)
35         cout<<0;
36     else
37         cout<<s;
38     return 0;
39 }