生日蛋糕 POJ – 1190
原创
wx62a9af7b9205e博主文章分类：搜索 ©著作权
文章标签 DFS poj #include 最优解 i++ 文章分类 Hadoop 大数据
©著作权归作者所有：来自51CTO博客作者wx62a9af7b9205e的原创作品，请联系作者获取转载授权，否则将追究法律责任
还是有些迷。。留坑
前两个剪枝是看在当前情况下能不能构成一个蛋糕
第三个剪枝是看当前情况下能不能形成最优解
using namespace std;
int prevv[50],press[50];
int vv,ll,ans;
void init()
{
int i;
for(i=1;i20;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-v<prevv[l]||ans-s<press[l]) return;
if(l<ll&&2*(vv-v)/r>ans-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;
}
- 赞
- 收藏
- 评论
- *举报
上一篇：炮兵阵地 POJ – 1185
Original: https://blog.51cto.com/u_15686209/5386270
Author: wx62a9af7b9205e
Title: 生日蛋糕 POJ – 1190
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/517310/
转载文章受原作者版权保护。转载请注明原作者出处！