首页 > 代码库 > poj 1190 生日蛋糕 , 强剪枝

poj 1190 生日蛋糕 , 强剪枝

题意:

制作一个体积为Nπ(N<=10000)的M(M<=20)层生日蛋糕,每层都是一个圆柱体。

 

设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。

当i < M时。要求Ri > Ri+1且Hi > Hi+1。

 
因为要在蛋糕上抹奶油。为尽可能节约经费。我们希望蛋糕外表面(最下一层的下底面除外)的面积Q最小。 
令Q = Sπ 
请编程对给出的N和M,找出蛋糕的制作方案(适当的Ri和Hi的值),使S最小。

 

(除Q外,以上全部数据皆为正整数) 


分析:

表面积仅仅和底面圆面积和各层側面积有关

Q = Sπ

S = R1*R1 + 2*sigma(Ri*Hi(1<=i<=M))

N = sigma(Ri*Ri*Hi(1<=i<=M))


状态(i, Ri, Hi, Si-1, Di-1)  转移---> (i+1, Ri+1, Hi+1, Si, Di)

枚举变量 Ri,Hi,为了降低状态数,就要降低Ri,Hi的枚举范围。

最初一定有: 

M-i<= Ri+1< Ri

M-i<= Hi+1< Hi


剪枝一:

预先计算

minS[i]  表示从上到下第一层到第i层最少要用去的S

minN[i]  表示从上到下第一层到第i层最少要用去的N

则有剪枝:

     Si-1 +minS[m-i] >= best   //最优化剪枝

     Di-1 + minN[m-i] >= N      //可行性剪枝


剪枝二:

从k层到m层添加的側面积

技术分享

Si-1 + 2*(N-Di-1)/Ri >=  best  //最优化剪枝


剪枝三:

假设先枚举Ri, 则Hi的上界 maxH = min(Hi  -1, N  -   Si-1   -   minN[M-i-1]) / (Ri*Ri)   )   //可行性剪枝

//先枚举Hi一样。


#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <map>
using namespace std;

#define min(a,b) (a) <(b) ?

(a):(b) #define INF 0x3f3f3f3f int minN[25], minS[25]; int N, M, Min; void init() { int i; minN[0] = minS[0] = 0; for(i=1; i<=21; ++i) { minS[i] = minS[i-1] + 2 * i * i; minN[i] = minN[i-1] + i * i * i; } } void dfs(int k, int r, int h, int sums, int sumv) { if(k==M){ if(sumv == N && sums < Min) { Min = sums; } return ; } if(sums + minS[M-k] > Min ||sumv + minN[M-k] > N||2*(N-sumv)/r + sums >= Min) return ; for(int i=r-1; i>=M-k; --i) { if(k==0) sums = i * i; int maxH = min( h-1, (N-sumv-minN[M-k-1])/(i*i) ); for(int j=maxH; j>=M-k; --j) dfs(k+1, i, j, sums + 2 * i * j, sumv + i * i * j); } } int main() { init(); while(cin>>N>>M) { Min = INF; dfs(0, N, N, 0, 0); //K, R, H, SUMS, SUMV if(Min<INF) cout<<Min<<endl; else cout<<0<<endl; } return 0; }




poj 1190 生日蛋糕 , 强剪枝