生日蛋糕 POJ - 1190

生日蛋糕 POJ - 1190

还是有些迷。。留坑

前两个剪枝是看在当前情况下能不能构成一个蛋糕

第三个剪枝是看当前情况下能不能形成最优解

#include #include #include #include using namespace std;#define N 0x3f3f3f3fint prevv[50],press[50];int vv,ll,ans;void init(){ int i; for(i=1;i<=20;i++) { prevv[i]=prevv[i-1]+i*i*i; press[i]=press[i-1]+2*i*i; } return;}void dfs(int r,int h,int l,int s,int v){ int i,j,maxx; if(l==0) { if(v==vv) { ans=min(ans,s); } return; } if(vv-vans-s) return; for(i=r;i>=l;i--) { if(l==ll) { s=i*i; } maxx=(vv-prevv[l-1]-v)/(i*i); for(j=min(maxx,h);j>=l;j--) { dfs(i-1,j-1,l-1,s+2*i*j,v+i*i*j); } } return;}int main(){ int i,j; init(); while(scanf("%d%d",&vv,&ll)!=EOF) { ans=N; dfs((int)sqrt(vv),vv,ll,0,0); printf("%d\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。