台州网站建设多少钱,网站开发获取本地ip,合肥优化排名推广,中国住建网查询资质题目
题目链接 自己没看题解写的#xff0c;摸石头过河#xff0c;解释一下
首先#xff0c;输入输出都是正整数。先搞定输入#xff0c;再判断条件#xff0c;如果无解#xff0c;输出0#xff0c;否则输出蛋糕外表面面积Q#xff08;这里用全局变量#xff0c;开l…题目
题目链接 自己没看题解写的摸石头过河解释一下
首先输入输出都是正整数。先搞定输入再判断条件如果无解输出0否则输出蛋糕外表面面积Q这里用全局变量开long long。
然后写dfs函数函数形参先写了一个layer, r, h。这些数据是需要递归时传入的在每一次的搜索中r,h都会变。
先写结束条件搜索层数layer与输入层数m相同时return结束。后来写着写着又在形参加了两个变量一个是奶油面积total_CreamArea蛋糕外表面面积一个是搜索中的总体积。结束条件中另外再加一个判断就是当总体积totalvolume n时取Q和奶油面积total_CreamArea的最小值来更新Q的值
写到这里就有问题了遇到瓶颈。这个rh的范围是多少呢
#include bits/stdc.h
using namespace std;int n, m; //蛋糕体积层数
long long Q 9e10;void dfs(int layer, int r, int h,int total_CreamArea, int totalvolume)
{if(layer m) //层数 输入层数{if(totalvolume n)Q min(Q, total_CreamArea);return; //结束dfs}//for(int i r; i0; i--)int newArea total_CreamArea 2*r*h; //加上侧面积底面积就是第一层的大圆面积int newVolume totalvolume r*r*h; //加上新一层的体积dfs(layer1, r, h, newArea, newVolume);
}int main()
{cinnm;dfs(1, )if(Q 9e10)cout 0 endl;elsecout minvolume endl;
}
后来看了视频还有罗老师的博客才知道原来是这样确定r, h的范围的。当然剪枝也是不能少的没有剪枝就会超时。
我是推不出来这个条件2(n−v)/rs≥ans测试过没有这个条件也有70分 版权声明本文为博主原创文章遵循 CC 4.0 BY-SA 版权协议转载请附上原文出处链接和本声明。 原文链接https://blog.csdn.net/weixin_43914593/article/details/135489983
【AC参考代码】
#include bits/stdc.h
using namespace std;int n, m; //蛋糕体积层数
int Q 9e8;
int minVolume[16], minArea[16]; //用于剪枝void dfs(int layer, int r, int h,int total_CreamArea, int totalvolume)
{if(layer 0) //层数 输入层数{if(totalvolume n)Q min(Q, total_CreamArea);return; //结束dfs}if(minVolume[layer] totalvolume n || totalvolume n) //体积大于输入值return;if(total_CreamArea minArea[layer] Q) //面积比最小面积还要大舍去return;if(2*(n - totalvolume)/r total_CreamArea Q) //2(n−v)/rs≥ansreturn;for(int newR min(r-1, (int)(sqrt(n-totalvolume)) ); newR layer; newR--){if(layer m) //上表面积从上往下看就是一个圆total_CreamArea newR * newR;//体积公式求hfor(int newH min(h-1, (n-totalvolume)/(newR * newR) ); newH layer; newH--){int newArea total_CreamArea 2*newR*newH; //加上侧面积底面积就是第一层的大圆面积int newVolume totalvolume newR*newR*newH; //加上新一层的体积dfs(layer-1, newR, newH, newArea, newVolume);}}}int main()
{cinnm;for(int i1;im;i){minVolume[i] minVolume[i-1] i*i*i; //R^3minArea[i] minArea[i-1] 2*i*i; //2*R^2}dfs(m, 9e8, 9e8, 0, 0);if(Q 9e8)cout 0 endl;elsecout Q endl;
}
看视频吧视频肯定比我讲得清楚。视频链接【B24 DFS剪枝 生日蛋糕】
