制作一个体积为 nπ 的 m 层生日蛋糕，每层都是一个圆柱体。设从下往上数第 i 层蛋糕是半径 Ri、高度为 Hi 的圆柱。要求 Ri > Ri+1 且 Hi > Hi+1。由于要在蛋糕商抹奶油，所以为了尽可能节约经费，希望蛋糕外表面面积 Q 最小。令 Q = Sπ,对给出的 N 和 M，找出蛋糕的制作方案，使 S 最小。除了 Q 外，以上所有数据皆为正整数。
#include <iostream> #include <cmath> using namespace std; int n,m; int ans=10000; int va[20]; void dfs(int u,int v,int s,int r0,int h0) { //u层，v当前体积，s当前体积， if(u==m) { //r0半径，h0高度 if(v==n){ if(ans>s){ ans=s; } } return; } if(va[m-u]+v>n){ return; } if(2.0*(n-v)/r0+s>ans){ return; } for(int i=r0;i>=m-u;i--){ for(int j=h0;j>=m-u;j--){ int tv=v+i*i*j; if(tv>n){ continue; } int ts=s+2*i*j; if(u==0){ ts+=i*i; } dfs(u+1,tv,ts,i-1,j-1); } } } int main(){ cin>>n>>m; //n为体积 ,m层 for(int i=1;i<=m;i++){ va[i]=va[i-1]+i*i*i; } int r0=sqrt(n)+0.5; dfs(0,0,0,r0,n); if(ans==10000){ ans=0; } cout<<ans; return 0; }
