题解P0006：生日蛋糕（P1731）

这道题居然是1999年省选题！这可能是洛谷蓝题里最水的了。。。

题目链接：https://www.luogu.com.cn/problem/P1731　　大家有兴趣可以去看看

题目描述：就是类似这样一个蛋糕：

 现在给它体积和层数，为了省奶油，要求它最小表面积（不算底面）

题目思路：深搜剪枝，从下到上枚举每层的半径和高，最终求出最小表面积（具体思路和剪枝详见代码注释）

代码：

#include<bits/stdc++.h>
using namespace std;
int r[21],h[21],n,m,we=0x3f3f3f3f;//定义数组存储半径和高是为了省事 
void dfs(int v,int s,int k,int p){//v：体积；s：表面积；k和p：层数（一个倒着的一个正着的） 
	int i,j;
	//下面是剪枝，可以最后看 
	if(v<0){//体积超了 
		return;//返 
	} 
	if(k<0){//层数超了 
		return;//返 
	}
	if(s+k+r[1]*r[1]>we){//表面积超了当前最小值，再往下搜没意义了 
		return;//返 
	}
	if(v>r[p-1]*r[p-1]*h[p-1]*k){//假设之后的体积全=当前体积，还是不够 
		return;//返 
	}
	//剪枝结束 
	if(k==0&&v==0){//满足条件 
		s+=r[1]*r[1];//加上最下面的底面积（=所有层有用的底面积） 
		we=min(we,s);//取最小值 
		return;
	}
	for(i=r[p-1]-1;i>=k;i--){//枚举半径（i的初始值是上一层-1） 
		for(j=h[p-1]-1;j>=k;j--){//枚举高 
			if(v>=i*i*j&&k>=0){
				r[p]=i;
				h[p]=j;
				dfs(v-i*i*j,s+2*i*j,k-1,p+1);//v减去当前层体积，s加上侧面积 
				r[p]=i;//回溯 
				h[p]=j;
			}
		}
	}
}
int main(){
	cin>>n>>m;
	h[0]=int(sqrt(n));
	r[0]=int(sqrt(n));//手动确定最底层高和半径的最大值 
	dfs(n,0,m,1);
	if(we==0x3f3f3f3f){//若值不变 
		cout<<0;//输出0 
	}else{
		cout<<we;
	}
	return 0; 
}