对于这一题首先可以想到一些明显的剪枝策略：
1、 从下往上数第i层Ri、Hi至少为m-i+1，因为要至少保证上面几层可以有的选择；
2、 比已出解大，剪枝；
3、 假设第i层半径为Ri、高为Hi，则i+1层半径最多为Ri-1，高最多为Hi-1，考虑极端的情况，那就是剩余m-i层半径都为Ri-1，高都为Hi-1，如果这样还达不到体积n，需要剪枝；
4、 考虑最小的情况，从i+1层到m层全部为1，如果这样还大于体积n，需要剪枝；
5、 第1层的情况，极端情况为高是1，此时半径最大sqrt(n)；半径为1,高最大n，这是搜索的边界
6、 假设前i层体积为nowv，表面积为nows，第i层半径为Ri，则如果2*(n-nowv)/rr+nows>=已出解，需要剪枝。这一点有空将给出证明。
以下是我的代码：
#include<stdio.h>
#include<math.h>
long n,m,ans=200000000;
void dfs(long dep,long nowv,long nows,long rr,long hh)
{// 前dep层蛋糕体积为nowv 表面积为nows 第dep层半径rr 高度hh
if(dep>=m)
{
if(nowv==n&&nows<ans)
ans=nows;
return;
}
if(nowv+(rr-1)*(rr-1)*(hh-1)*(m-dep)<n) return;// 每层最大都达不到体积
if(nowv+m-dep>n) return;// 每层最小都超过体积
if(2*(n-nowv)/rr+nows>=ans) return;// 不等式放缩法剪枝
long i,j;
for(i=rr-1;i>=m-dep;i--)
for(j=hh-1;j>=m-dep;j--)
if(nows+2*i*j<ans)// 比已出解小
dfs(dep+1,nowv+i*i*j,nows+2*i*j,i,j);
}
int main()
{
FILE *fin,*fout;
long i,j;
fin=fopen("cake.in","r");
fscanf(fin,"%ld%ld",&n,&m);
fclose(fin);// Read In
for(i=m;i<=sqrt(n);i++)
for(j=m;j<=n;j++)
dfs(1,i*i*j,i*i+2*i*j,i,j);
fout=fopen("cake.out","w");
fprintf(fout,"%ld\n",ans);
fclose(fout);
return 0;
}
posted on 2010-01-06 19:44
lee1r 阅读(1164)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：搜索