【解题报告】 [NOI1999]生日蛋糕

题目：生日蛋糕

解题思路：

dfs枚举

这道题上面的表面积不用管，只用管侧面积和体积，上面的表面积就是最底下的圆的面积

我们只需要枚举半径和高度就OK了

另外需要剪枝，如果枚举到dep-1层时，最小体积大于n的话，我们就可以进行剪枝了

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=0x3f3f3f;
const int N=20007;
int ans=maxn;
int mins[N],minv[N],n,m;
void dfs(int now,int r,int h,int s,int v)
{
	int mh=h;
	if(now==0)
	{
		if(v==n)
		ans=min(ans,s);
		return ;
	}
	if(s+mins[now-1]>=ans)
	return ;
	if(v+minv[now-1]>n)
	return ;
	if(2*(n-v)/r+s>=ans)
	return ;
	for(int i=r-1;i>=now;i--)
	{
		if(now==m)
		s=i*i;
		mh=min(h-1,(n-minv[now-1]-v)/i/i);
		for(int j=mh;j>=now;j--)
		dfs(now-1,i,j,s+2*i*j,v+i*i*j);
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		mins[i]=mins[i-1]+2*i*i;
		minv[i]=minv[i]+i*i*i;
	}
	dfs(m,n,n,0,0);
	if(ans==maxn)
	cout<<0<<endl;
	else
	cout<<ans<<endl;
	return 0;
}