首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

DFS--POJ 1190 生日蛋糕

Description 7月17日是Mr.W的生日,ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕,每层都是一个圆柱体。 设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时,要求Ri > Ri+1且Hi > Hi+1。 由于要在蛋糕上抹奶油,为尽可能节约经费,我们希望蛋糕外表面(最下一层的下底面除外)的面积Q最小。 令Q = Sπ 请编程对给出的N和M,找出蛋糕的制作方案(适当的Ri和Hi的值),使S最小。 (除Q外,以上所有数据皆为正整数) Input 有两行,第一行为N(N <= 10000),表示待制作的蛋糕的体积为Nπ;第二行为M(M <= 20),表示蛋糕的层数为M。 Output 仅一行,是一个正整数S(若无解则S = 0)。 Sample Input 100 2 Sample Output 68 Solution 由于深度一定(m),所以使用深度优先搜索,自上而下的设定蛋糕序号,最顶层的为第1层,……,最底层的蛋糕为第m层,很明显满足题目条件的前i层的(从顶层(也就是编号为1的层)开始计数)最小面积mins[i]和体积minv[i]是在该层的半径以及高度都为i时取得,如果采用一般的神搜肯定会超时,所以这题还需要剪枝,剪枝条件有(从m层向上搜,假设前level层的体积为v,面积为s,当前所得的最小面积为best): 1>因为前level层的体积为v,如果剩下的几层的体积都取最小可能值,总体积还是比n大,那么则说明前level层的方案不可行,所以可以剪枝(剪枝条件为:v+minv[dep-1]>n) 2>因为前level层的面积为s,如果剩下的几层的面积都取最小可能值,所得的面积和比已经得到的所求的最小面积best大,也可以进行剪枝(剪枝条件为:s+mins[dep-1]>best) 3>因为前level层的体积为v,那么剩余的m-level层的体积满足:n-v=(hk+……+hm)(k=level+1,……,m) 而剩余部分的表面积满足:lefts=2*(r[k]h[k]+……+r[m]h[m])>2(n-sv)/r[level] (k=level+1,……,m) 显然有上述不等式lefts=best-s>2(n-)/r,即2*(n-v)/r+s

01

墨卡托投影坐标系(Mercator Projection)原理及实现C代码

墨卡托投影是一种“等角正切圆柱投影”,荷兰地图学家墨卡托(Mercator)在1569年拟定:假设地球被围在一个中空的圆柱里,其赤道与圆柱相接触,然后再假想地球中心有一盏灯,把球面上的图形投影到圆柱体上,再把圆柱体展开,这就是一幅标准纬线为零度(即赤道)的“墨卡托投影”绘制出的世界地图。   墨卡托投影在今天对于航海事业起着极为重要的作用,目前世界各国绘制海洋地图时仍广泛使用墨卡托投影,国际水路局(IHB)规定:“除特殊情况外,各国都要用墨卡托投影绘制海图”。国际水路局发行的《大洋水深总图》是把全世界分

05
领券