下面注释的三个地方为剪枝......

(附代码,仅供交流...)
#include<iostream>
using namespace std;
#include<stdio.h>
#define MAX 100000
const int maxr=25;
const int maxh=25;
int n,m;
int mins;
int minv[26],maxv[26][26];
void set()
{
	int i,j;
	minv[0]=0;
	for(i=1;i<=maxr;i++)
	{
		minv[i]=minv[i-1]+i*i*i;
	}
	for(i=0;i<=maxr;i++)
	{
		maxv[i][0]=0;
		maxv[0][i]=0;
	}
	for(i=1;i<=maxr;i++)
		for(j=1;j<=maxr;j++)
		{
			maxv[i][j]=maxv[i-1][j-1]+i*i*j;
		}
}
void search(int floor,int r,int h,int v,int s)
{
	v-=r*r*h;
	s+=2*r*h;
	if(floor==m)
	{

		if(v==0)
		{
			if(s<mins)
				mins=s;
		}
		return;
	}
	if(v<=0||s>mins)	//剪枝,当前所得到的总面积大于已求得最小总面积,或剩余体积小于0
		return;
	int i,j;
	floor++;
	int left=m-floor+1;

	if((maxv[r-1][h-1]-maxv[r-left-1][h-left-1])<v) //剪枝,剩余体积大于当层以上的所有层的最大体积和
		return;

	if(minv[left]>v)	//剪枝,剩余体积小于当层以上的所有层的最小体积和
		return;

	for(i=r-1;i>=left;i--)
		for(j=h-1;j>=left;j--)
		{
			search(floor,i,j,v,s);
		}
}
int main()
{
	int i,j;
	set();
	while(scanf("%d%d",&n,&m)==2)
	{
		mins=MAX;
		for(i=maxr;i>=m;i--)
			for(j=maxh;j>=m;j--)
			{
				search(1,i,j,n,i*i);
			}
		if(mins==MAX)
			printf("0\n",mins);
		else
			printf("%d\n",mins);
	}
	return 0;
}

• Re:请教这道题还有哪些地方可以剪枝啊,我找了三个地方,不过还要46ms,看到很多人0秒过的......... (1448) o00o 2007-11-15 14:52:59
• Re:请教这道题还有哪些地方可以剪枝啊,我找了三个地方,不过还要46ms,看到很多人0秒过的......... (1483) JRuby 2007-12-08 21:26:44
• Re:请教这道题还有哪些地方可以剪枝啊,我找了三个地方,不过还要46ms,看到很多人0秒过的......... (1404) oceanwolf 2009-07-27 22:55:34