首页 > 代码库 > poj1190 生日蛋糕（深搜+剪枝）
poj1190 生日蛋糕（深搜+剪枝）
题目链接：poj1190 生日蛋糕解题思路：深搜，枚举：每一层可能的高度和半径确定搜索范围：底层蛋糕的最大可能半径和最大可能高度搜索顺序：从底层往上搭蛋糕，在同一层尝试时，半径和高度都是从大到小试剪枝：①已建好的面积已经超过目前求得的最优表面积，或者预见到搭完后面积一定会超过目前最优表面积，则停止搭建（最优性剪枝）②预见到再往上搭，高度已经无法安排，或者半径无法安排，则停止搭建（可行性剪枝）③还没搭的那些层的体积，一定会超过还缺的体积，则停止搭建（可行性剪枝）④还没搭的那些层的体积，最大也到不了还缺的体积，则停止搭建（可行性剪枝）看讨论时看见了一个神剪枝：当2 * leftVolume / r + currentS >= min停止搜索currentS代表“已有的圆柱的侧面积之和+最底下圆柱的横截面面积”。min代表已得到的最小表面积。假设只有一个圆柱，该圆柱的半径为r,体积为leftVolume，可知：2 * leftVolume/r 表示圆柱的侧面积。现在我们有2个圆柱，要求这两个圆柱叠在一起之后满足题目的条件：下柱半径>上柱半径。把上柱压扁，压到和下柱的半径相等，那么根据表面积和体积公式，我们知道上柱的侧面积会减小。多个圆柱叠立，假设最下面圆柱半径最大，该半径为r。于是，这些圆柱的侧面积之和>=等体积的半径为r的圆柱的侧面积。假设还有k层柱要搜索，leftVolume是剩余体积，r是第k层的圆柱的最大可能半径。那么2*leftVolume/r<=k层圆柱的最小侧面积之和。
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #define CLR(a,b) memset((a),(b),sizeof(a)) 7 using namespace std; 8 9 const int inf = 0x3f3f3f3f;10 int ans; //最优表面积11 int area; //正在搭建中的蛋糕的表面积12 int N, M;//体积N,层数M13 int minv[21]; //第i层蛋糕最少的体积14 int mins[21]; //第i层蛋糕的最少侧表面积15 16 int maxV(int n, int r, int h){17 //在n层蛋糕，底层最大半径r,最高高度h的情况下，能凑出来的最大体积18 int v = 0;19 for(int i = 0; i < n; ++i)20 v += (r - i) * (r - i) * (h - i);21 return v;22 }23 void dfs(int v, int n, int r, int h){24 //用n层去凑体积v，最底层半径最大为r, 高度最大为 h25 //求出最小表面积放入ans26 if(n == 0){27 if(v == 0 && area < ans){28 ans = area;29 return;30 }31 }32 if(v <= 0) return;33 34 if((2*v*1./r+area)>=ans) return;35 if(area + mins[n] >= ans ) return;36 if(h < n || r < n) return;37 if(v < minv[n]) return;38 if(maxV(n, r, h) < v) return;39 for(int rr = r ; rr >= n; --rr){//从大到小搜索!40 if(n == M) //底面积(总的上表面积)41 area = rr * rr;42 for(int hh = n; hh <= h; ++hh){43 area += 2 * rr * hh;44 dfs(v - rr*rr*hh, n-1, rr-1, hh-1);45 area -= 2 * rr * hh;46 }47 }48 }49 int main(){50 int i, j;51 int maxh;//底层最大高度52 int maxr;//底层最大半径53 scanf("%d %d", &N, &M);54 55 CLR(minv, 0); CLR(mins, 0);56 57 for(i = 1; i <= M; ++i){58 //第i层半径至少为i，，高度至少为i59 minv[i] = minv[i - 1] + i * i * i;60 mins[i] = mins[i - 1] + 2 * i * i;61 }62 if(minv[M] > N){63 printf("0\n"); return 0;64 }65 area = 0;66 ans = inf;67 //底层体积不超过(n - minv[m - 1])68 maxh = (N - minv[M - 1]) / (M * M) + 1; //底层半径至少为 m69 maxr = sqrt(1.*(N - minv[M-1]) / M) + 1;//底层高度至少为 m70 71 dfs(N, M, maxr, maxh);72 73 if(ans == inf) printf("0\n");74 else printf("%d\n", ans);75 return 0;76 }
poj1190 生日蛋糕（深搜+剪枝）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。