對于這一題首先可以想到一些明顯的剪枝策略：
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 閱讀(1183)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索