本人的原文章出处: https://blog.csdn.net/qq_43093454/article/details/100055362
题面
题目背景
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
理清题面
- 给出的条件是体积为n,层数是m层;
- 之后要求的是使得最小的表面积Q=sπ的最小的s的值;
- 程序需要做的事情是依次的确定每一层的半径R和高度H;
- 蛋糕的面积包括的是所有层的裸露的部分的面积(这个面积等价于最后一层的下表面积)和所有的侧面积;
- 所有层的裸露的部分的面积可以在m层的时候就直接加上。
从零分到达ac的心路历程
一开始的时候,就是完全没有思路,更像是没有这道题的方向,这道题应该要往哪方面入手,我不知道,我也没有想出来。
之后我看见了题目中有若s无解则s等于0,所以我直接输出了0。但是0分,脑子一想,发现自己真的没谁了,怎么可能会有无解的情况,只要n,m给定了,基本上整个蛋糕的雏形就已经出现了,那么就肯定会是有解的啊!!所以绝对不可能会有s=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;
}
心路完了。
思路
思路呢,还是要好好想想的,下回在更。(已补更)
- 由于深度一定(m),所以使用深度优先搜索;
- 就像是上面的题面理解上说的那样,程序要做的就是一个个试试,判断自己此时的半径和高度是否合法;
- 但是思考一下即使m只有15,若是把所有的情况(所有的半径和高都找出来并且达到相互匹配的地步)一一都列举出来的话,也还是会超时,所以要考虑所有的可行的剪枝;
- 考虑剪枝:
- 搜索顺序上的剪枝:从体积大的盘子搜到体积小的盘子。(这样的话若是方案不合法在一个大的的时候就可以直接扔掉不要,但是如果是小的的话,可能就要试很多个。)
- 可行性剪枝1:当 当前的体积+之后预测到的自己认为的最优的体积>n 的时候就可以直接舍弃这一个不合法的方案。(当前的加上最优的都已经是不合法的了,还能怎么办?)
- 可行性剪枝2:上下界剪枝。根据多年的数学学习把半径和高度的冗余的状态全部都丢掉不要。(数学公式回来再补充)
- 最优性剪枝1:在dfs的过程中可能会有很多次搜索到不合法的方案,若是不合法的方案用到的面积刚好等于n的时候(也就是说给定的面积全部都用完了),那么最优解的ans一定小于此时的答案,这个时候在ban掉这个方案之前可以对答案进行进一步的更新;
- 最优性剪枝2: 若 当前的面积+之后预测到的自己认为的最优的面积>ans 的时候就可以直接舍弃这一个不优秀的方案,因为他没有答案小。
- 还有一个鬼畜剪枝,如上一份代码中的标注。(回来再更)
之后就要考虑上面挖的坑了:
如何找到自己认为的最优的体积/面积?
-
思考一下,若此时已经给了蛋糕的轮廓,那么在不考虑体积的情况下,怎么样才会最优?
- 使得当前的蛋糕最小;
- 使得上下层之间的蛋糕的差距最小(最好是只相差1)
-
那么根据上面的两点我们就可以做出预处理,我们把最小的一层的半径和高度都定做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学长一个问题:为什么生日蛋糕这道题需要用搜索写?我拿到题的时候就压根没有想过搜索这一方面,换句话说,怎么知道一道题是搜索题?
学长如是说:
- 首先看一下这道题想不想你写过的图论,DP,数据结构等一些算法;
- 其次再看一下这道题想不想你写过的某一道鬼畜题;
- 然后审查一番这道题有没有想自己曾经写过的某一类搜索题;
- 最后若都不是的话,就往搜索方面想。
补充:put使用的时候不可以是put(0)
应该是put("0")
。
未完待更。。。
%%% 非常棒的题解
有可能无解吧。。比如n<m的时候
菜b
好像mins【】的初始化有点问题,是不是少了一个系数2:2 * i * i,不过问题不大,只是有些枝没减掉。
xdu?
题解太良心了 不得不说 顶顶顶!
##同样是小蓝书,为什么你的书更吊(滑稽)
嘿嘿嘿。(滑稽)
# 和光盘上的一模一样啊
嗯,我就是照着蓝皮书学的。
但是,你再看一下确定是一模一样吗?这个博客里有我的理解,有我看到这道题的理解,有我写这道题的感受,有我问学长的问题以及自己的总结。如果这样子还说是一模一样,那么我也就没有办法了,毕竟我确实是照着蓝皮书学的。如果你看我博客的话,其中就有一篇剪枝的总结,说的就是,我就是在向蓝皮书学习,只是这里面有我自己的感受,主体内容还是蓝皮书上的知识,所以我总结到了博客里。书上的是别人的,我学会了并且消化吸收之后就是我自己的东西,博客不就是用来记新学的东西的吗?而且我从来没有否认过蓝皮书的原版。
不好意思,是我误会了
啊,没事没事,嘿嘿,我的反应也是有点激烈了,还是希望你见谅啊!
哈哈哈,你好可爱