生日蛋糕

Time Limit:?1000MS	?	Memory Limit:?10000K
Total Submissions:?16191	?	Accepted:?5751

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

Hint

圓柱公式?
體積V = πR²H?
側面積A' = 2πRH?
底面積A = πR²?
解題思路：首先肯定是對于每一層，枚舉R和H，接下來就是剪枝了，如果當前剩余的體積比能夠取到的最小的體積還要小，那么肯定不要再搜下去了；如果當前的表面積已經比已知的最小面積還要大，剪枝（這點很容易想到）；如果當前得到的表面積+之后能夠得到的最小的表面積＞已知的最小面積，剪枝（這一點很難想，假設已經涂了s，那么還剩下rest_s = sum{2*Ri*Hi} >= sum(2*Ri*Ri*Hi/Rk} = 2*(V-v)/r （設k為當前層的半徑））。
AC: #include<iostream> #include<cstdio> #include<cstring> using namespace std;const int inf = 0x3f3f3f3f; int n,m,ans,tmp,sumv[30];void dfs(int v,int dep,int R,int H) {if(dep == 0){if(v == 0 && ans > tmp) ans = tmp;return;}if(v - sumv[dep-1] < 0 || tmp >= ans || 2*v/R + tmp >= ans) return;for(int r = R-1; r >= dep; r--){int Hm = min(H-1,(v-sumv[dep-1])/r/r);for(int h = Hm; h >= dep; h--){if(dep == m) tmp = r*r;tmp += 2*r*h;dfs(v-r*r*h,dep-1,r,h);tmp -= 2*r*h;}} }int main() {sumv[1] = 1;for(int i = 2; i <= 20; i++)sumv[i] = sumv[i-1] + i*i*i;while(scanf("%d%d",&n,&m)!=EOF){ans = inf;dfs(n,m,n+1,n+1);printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的poj 1190(剪枝)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。