本文主要是介绍poj1190 生日蛋糕 dfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：生日蛋糕有m层，总体积是V。从下向上，每一层的半径r和高度h都是递减的。
给m、v，求最小的表面积s。（不算底面接地的面积）
题目链接：poj1190
剪枝都还没加。。样例输出都是错的。。。还没找到问题。。。
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;int ans,V,M,flag,s;int dfs(int v,int m,int newr,int newh)
{int r,h,tmp,i;if(m==0){flag=1;if(v==0&&s<ans) ans=s;return 0;}for(i=1,tmp=0;i<=m;i++)//若之后每层都取最小值tmp+=(i*i*i);if(tmp>v) return 0;//依然大于剩余的v 那么一定不可能tmp-=(m*m*m);for(r=newr;r>=m;r--){for(h=newh;h>=m;h--){//for(i=0,tmp=0;i<m;i++)//每层取最大值 //这个剪枝加了也有问题// tmp+=(r-i)*(r-i)*(h-i);//if(v>tmp) break;//依然小于v 也不可能if(m==M) s+=r*(2*h+r);else s+=2*r*(h+r);if(s<ans) dfs((v-(r*r*h)),m-1,r-1,h-1);if(m==M) s-=r*(2*h+r);else s-=2*r*(h+r);}}return 0;
}int main()
{while(~scanf("%d%d",&V,&M)){ans=inf;s=0;flag=0;dfs(V,M,1000,1000);printf("%d\n",flag?ans:0);}return 0;
}
这篇关于poj1190 生日蛋糕 dfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
