POJ1190生日蛋糕

Posted on | In |

题意

要制作一个体积为N π 的M层生日蛋糕，每层都是一个圆柱体。
设从下往上数第i(1 <= i <= M)层蛋糕是半径为R i , 高度为H i 的圆柱。当i < M
时，要求R i > R i+1 且H i > H i+1 。

由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的
下底面除外）的面积Q最小。

令Q = Sπ请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。
（除Q外，以上所有数据皆为正整数）

思路

深度优先搜索，枚举每一层可能的高度和半径。

确定搜索范围: 底层蛋糕的最大可能半径和最大可能高度

剪枝

  • 剪枝1：搭建过程中发现面积超过已经求得的最优表面积，则停止搭建

  • 剪枝2：搭建过程中预见到再往上搭，高度已经无法安排，或者半径已
    经无法安排，则停止搭建

  • 剪枝3：搭建过程中发现还没搭的那些层的体积，一定会超过还缺的体
    积，则停止搭建

  • 剪枝4：搭建过程中发现还没搭的那些层的体积，最大也到不了还缺的
    体积，则停止搭建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<algorithm>
#include<cmath>

#define MAX 100 
using namespace std;
int minV[MAX];
int minA[MAX]; 
int area;
int m,N;
int minArea=1<<30;
int maxNRH(int n,int r,int h){
	int v=0;
	for(int i=0;i<n;i++){
		v+=(r-i)*(r-i)*(h-i);
	}
	return v;
} 
//用n层去凑体积v 最底层半径不超过r 高度不超过h 
//入 求出最小表面积放入 minArea
void dfs(int n,int v,int r,int h){ 

	if(n==0) {
		if(v) return;
		else{
		minArea=min(minArea,area); 
		return;
	}} 
		if(v<0) return;//!!
	if(minV[n]>v) return;
	if(area+minA[n]>=minArea) return ;
	if(r<n||h<n) return;
	if(maxNRH(n,r,h)<v) return;
//	if(n==m) area+=r*r//!!;

	for(int rr=r;rr>=n;rr--){
			if(n==m) area=rr*rr;//!!不能写成area+
		for(int hh=h;hh>=n;hh--){
			area+=2*rr*hh;
			dfs(n-1,v-rr*rr*hh,rr-1,hh-1);//!!
			area-=2*rr*hh;
		}
		
	}
}
int main(){
	//m层蛋糕体积为N 
	//freopen("cake.txt","r",stdin);
	cin>>N>>m;
	minA[0]=minV[0]=0;
	for(int i=1;i<=m;i++)
	{
		minV[i]=minV[i-1]+i*i*i;
		minA[i]=minA[i-1]+2*i*i; 
	}
	int R=sqrt(double((N-minV[m-1])/m))+1;
	int H=(N-minV[m-1])/(m*m)+1;
		
		//	for(int rr=R;rr>=m;rr--){ 错的地方 应该在dfs函数功能完成 
		//		for(int hh=H;hh>=m;hh--){
	area=0;
	dfs(m,N,R,H);

//		}
//	}
	if(minArea==1<<30) cout<<0<<endl;
	else cout<<minArea<<endl;
	return 0; 
}