poj 生日蛋糕 剪枝+dfs

头一次见这么夸张的剪枝操作。

这个点也很难想

2*r*h=S *

r*r*h=V * =>

V*2/r = S

S + sumS >= best => return;

#include <cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int best = 0x7ffffff;
const int maxn = 1e3+10;
int minv[maxn];
int n,m;
void dfs(int now,int sums,int sumv,int r,int h)
{
	if(now == 0)
	{
		if(sumv==n && best>sums) best = sums;
		return;
	}
	if(sumv+minv[now] > n) return;
	if(2*(n-sumv)/r+sums >= best) return;
	for(int i = r-1; i >= now; --i)
	{
		if(now==m) sums = i*i;
		for(int j = h-1; j >= now; --j)
		{
			dfs(now-1,sums+i*j*2,sumv+i*i*j,i,j);
		}
	}
}
int main()
{
	minv[0] = 0;
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= m; ++i) minv[i] = minv[i-1]+i*i*i;
	int maxh = (n-minv[m-1])/(m*m)+1;
	int maxr = sqrt((double)(n-minv[m-1])/m)+1;
	dfs(m,0,0,maxr,maxh);
	if(best==0x7ffffff) best = 0;
	printf("%d\n",best);
	return 0;	
}