[NOI1999]生日蛋糕（详细题解）

题面

题目背景
7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层
生日蛋糕，每层都是一个圆柱体。
设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i<M时，要求$R_i>R_{i+1}$且$H_i>H_{i+1}$。
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。
令Q= Sπ
请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。
（除Q外，以上所有数据皆为正整数）
输入输出格式
输入格式
有两行，第一行为N（N<=20000），表示待制作的蛋糕的体积为Nπ；第二行为M(M<=15)，表示蛋糕的层数为M。
输出格式
仅一行，是一个正整数S（若无解则S=0）。
输入输出样例
输入样例 #1
100
2
输出样例 #1
68

理清题面

1. 给出的条件是体积为n，层数是m层；
2. 之后要求的是使得最小的表面积Q=sπ的最小的s的值；
3. 程序需要做的事情是依次的确定每一层的半径R和高度H；
4. 蛋糕的面积包括的是所有层的裸露的部分的面积（这个面积等价于最后一层的下表面积）和所有的侧面积；
5. 所有层的裸露的部分的面积可以在m层的时候就直接加上。

从零分到达ac的心路历程

一开始的时候，就是完全没有思路，更像是没有这道题的方向，这道题应该要往哪方面入手，我不知道，我也没有想出来。

之后我看见了题目中有若s无解则s等于0，所以我直接输出了0，但是0分。脑子一想，发现自己真的没谁了，怎么可能会有无解的情况，只要n，m给定了，基本上整个蛋糕的雏形就已经出现了，那么就肯定会是有解的啊！！所以绝对不可能会有s=0的情况。 （被划掉的是作者之前的想法）

s是有可能等于0的（因为又做了一道题之后发现数据里面是有s==0这个答案的）
给个数据：
1000
7
答案是0。（暂时博主还有没想到为什么，愿看到这里的大佬倾情告知，待更）

之后，我就又磨了将近一天，发现不会，这什么玩意题啊，根本套不上我写的任何模板。。。

再之后，我就翻看了题解，噢~ 原来是dfs。。。看到是dfs之后，我就又开始自己想思路，毕竟我自己认为dfs什么的没有什么难度，之后就瞬间打脸，我连dfs从哪里下手都不知道，我真服了我自己了，估计又是自己自诩清高，没有真正地了解过什么才是dfs。

再之后，我就打开了我亲爱的蓝皮书，一字一字的翻看，结果还是看不懂，我就开始颓了，在海亮的时候就已经开始要着手打这道题的代码，但是这种状态一直持续到今天上午，我才敲完这道题，还是在磨着题解的情况下，我才敲完了这一道题。。

所以说，骚年，要“开始”学习dfs了。

分享一波我给蓝皮书的正解代码打的注释：

//Author:XuHt
#include <cmath> 
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x7fffffff;
int n, m;/*n，m是给定的体积以及层数*/
int minv[30], mins[30], ans = INF;
int h[30], r[30], s = 0, v = 0;void dfs(int dep) {if (!dep) {/*还在搜索的过程中*/if (v == n) ans = min(ans, s);/*体积已经全部用完了,此时的不合法的状态下的面积一定比合法的面积小*/return;}
/*sqrt(n - v):数学公式可以把半径进一步的缩小；
而r[dep + 1] - 1是因为当前dep层一定是比dep+1层小的,最少小一,这样子的话下面一层就会有更多的选择,h同r;
r[dep] >= dep是因为如果r小于dep的话,那么之后的层数一定不够m层,所以该结果不合法*/for (r[dep] = min((int)sqrt(n - v), r[dep + 1] - 1); r[dep] >= dep; r[dep]--)/*确定半径*/for (h[dep] = min((int)((double)(n-v) / r[dep] / r[dep]), h[dep+1] - 1); h[dep] >= dep; h[dep]--) {if (v + minv[dep-1] > n) continue;if (s + mins[dep-1] > ans) continue;if (s + (double)2 * (n - v) / r[dep] > ans) continue;/*鬼畜剪枝*//*用剩余体积估计之后的比实际要小的需要用到的表面积+s判断当前状态是否可行*/if (dep == m) s += r[dep] * r[dep];/*所有层的裸露的部分的面积*/s += 2 * r[dep] * h[dep];/*s=2rπh*/v += r[dep] * r[dep] * h[dep];/*v=r*r*πh*/dfs(dep - 1); if (dep == m) s -= r[dep] * r[dep];/*回溯的现场还原*/s -= 2 * r[dep] * h[dep];v -= r[dep] * r[dep] * h[dep];}
}int main() {cin >> n >> m;minv[0] = mins[0] = 0;/*初始化处理从上到下的每一层之前的最小的体积以及侧面积*/for (int i = 1; i <= m; i++) {minv[i] = minv[i-1] + i * i * i;/*有要求每一层的半径和高度都应该是逐个递增的*/mins[i] = mins[i-1] + i * i;}h[m+1] = r[m+1] = INF;/*因为一共只需要m层,在搜索的for循环中有体现*/dfs(m);/*搜索的顺序是从最大的一层到最小的一层*/cout << ans << endl;return 0;
}

心路完了。

思路

思路呢，还是要好好想想的，下回在更。（已补更）

1. 由于深度一定(m),所以使用深度优先搜索；
2. 就像是上面的题面理解上说的那样，程序要做的就是一个个试试，判断自己此时的半径和高度是否合法；
3. 但是思考一下即使m只有15，若是把所有的情况（所有的半径和高都找出来并且达到相互匹配的地步）一一都列举出来的话，也还是会超时，所以要考虑所有的可行的剪枝；
4. 考虑剪枝：
   1. 搜索顺序上的剪枝：从体积大的盘子搜到体积小的盘子。（这样的话若是方案不合法在一个大的的时候就可以直接扔掉不要，但是如果是小的的话，可能就要试很多个。）
   2. 可行性剪枝1：当 当前的体积+之后预测到的自己认为的最优的体积>n 的时候就可以直接舍弃这一个不合法的方案。（当前的加上最优的都已经是不合法的了，还能怎么办？）
   3. 可行性剪枝2：上下界剪枝。根据多年的数学学习把半径和高度的冗余的状态全部都丢掉不要。（数学公式回来再补充）
   4. 最优性剪枝1：在dfs的过程中可能会有很多次搜索到不合法的方案，若是不合法的方案用到的面积刚好等于n的时候（也就是说给定的面积全部都用完了），那么最优解的ans一定小于此时的答案，这个时候在ban掉这个方案之前可以对答案进行进一步的更新；
   5. 最优性剪枝2: 若 当前的面积+之后预测到的自己认为的最优的面积>ans 的时候就可以直接舍弃这一个不优秀的方案，因为他没有答案小。
   6. 还有一个鬼畜剪枝，如上一份代码中的标注。（回来再更）

之后就要考虑上面挖的坑了：

如何找到自己认为的最优的体积/面积？

1. 思考一下，若此时已经给了蛋糕的轮廓，那么在不考虑体积的情况下，怎么样才会最优？

   1. 使得当前的蛋糕最小；
   2. 使得上下层之间的蛋糕的差距最小（最好是只相差1）

2. 那么根据上面的两点我们就可以做出预处理，我们把最小的一层的半径和高度都定做1，之后的每一层依次加一，这样的话就是最优秀的/最小的了。

为什么这样子可行？

可以在思考一下，此时我们预处理出来的是体积最小的最优情况，那么若此时的状态加上最优的都不行的话，更何况是在给定的体积>=最优的体积的情况下呢？当然是答案只会比我们预测的要多而不会少。

注意在s没有被更新的情况下，输出0。

放一波代码

//Author:melody
#include<bits/stdc++.h>
using namespace std;const int maxx=0x7ffff;int n,m;
int minv[30],mins[30];
int h[30],r[30],ans=maxx;
int v,s;void dfs(int dep)
{if(!dep)/*剪枝3:所有的不合法方案也可以让ans缩小范围*/{if(v==n)	ans=min(ans,s);return ;}for(r[dep]=min((int)sqrt(n-v), r[dep+1]-1); r[dep]>=dep; r[dep]--)/*剪枝4:缩小上下边界*/for(h[dep]=min((int)((double)(n-v)/r[dep]*r[dep]), h[dep+1]-1); h[dep]>=dep; h[dep]--){if(v+minv[dep]>n)	continue;/*剪枝5:估计的最小面积比给定的大是不合法的*/if(s+mins[dep]>ans)	continue;/*剪枝6:估计的最小面积比当前答案大是不优秀的*/if(2*(n-v)/r[dep]+s>ans)	continue;/*剪枝7:鬼畜的数学剪枝*/if(dep==m)	s+=r[dep]*r[dep];s+=2*r[dep]*h[dep];v+=r[dep]*r[dep]*h[dep];dfs(dep-1);if(dep==m)	s-=r[dep]*r[dep];s-=2*r[dep]*h[dep];v-=r[dep]*r[dep]*h[dep];}
}int main()
{cin>>n>>m;for(int i=1;i<=m;++i)/*剪枝1:预处理最小的体积和表面积*/{minv[i]=minv[i-1]+i*i*i;mins[i]=mins[i-1]+i*i;}h[m+1]=r[m+1]=maxx;dfs(m);//剪枝2:搜索顺序的优化if(ans==maxx)	puts("0");else printf("%d\n",ans); return 0;
}

最后的知识小分享

我曾经问过cdqc学长一个问题：为什么生日蛋糕这道题需要用搜索写？我拿到题的时候就压根没有想过搜索这一方面，换句话说，怎么知道一道题是搜索题？

学长如是说：

1. 首先看一下这道题想不想你写过的图论，DP，数据结构等一些算法；
2. 其次再看一下这道题想不想你写过的某一道鬼畜题；
3. 然后审查一番这道题有没有想自己曾经写过的某一类搜索题；
4. 最后若都不是的话，就往搜索方面想。

补充：put使用的时候不可以是put(0)应该是put("0")。

未完待更。。。