我是在最后一层进行判断的，而不是第零层，所以第一次搜索（主函数中的搜索）比较特殊，WA了好多次……

/*
算法:搜索+ 剪枝
	minv[i] i层时的最小体积
	mins[i] i层时的最小体积
*/
#include <stdio.h>
#include <math.h>
#define MIN(x,y) ((x)<(y)?(x):(y))
#define INF 1000000
#define MAXR 25
#define MAXH 25

int minv[MAXH];
int mins[MAXR];
int n,m;
int ans = INF;

void build(){
	int i=1;
	minv[1] = 1;
	mins[1] = 2;
	for(i=2; i<MAXH; i++)
		minv[i] = minv[i-1] + i*i*i,
		mins[i] = mins[i-1] + 2*i*i;
};

void search(int level, int lastR, int lastH, int leftv, int s){ //还剩level层,前面的面积为s


	if( level == 0 ){
		if(0 == leftv && s < ans) ans = s ;
		
		return;
	}
	if (leftv <= 0 ) return ; //level>0 但是已经没有剩余体积了
	
	if( s + mins[level] >= ans || 2*leftv/lastR + s >= ans) return; 
	//！！剩下的面积一定大于原来得到的最小值了！！这一步剪枝最重要！！从TLE到16ms……
	
	if( leftv < minv[level]) return ; //剩下的体积太小了

	if( level == 1){ //最后一层
		if((lastR-1)*(lastR-1)*(lastH-1) < leftv) return; //剩下的体积太多了不可能了

	
		//int r = MIN( sqrt(leftv) , lastR-1);
		for(int r = lastR-1; r > 0; r--) //从大到小枚举所有的r
			if(0 == leftv % (r*r) && leftv/(r*r) < lastH ) { //可行解
				if( s + 2*leftv/r < ans){
					ans = s + 2*leftv/r ;  
					break; //第一个找到的可行解一定是最小的
				}
		}	
	}
	else{
		int i,j;
		for(i = lastR-1; i >= level; i--) //半径至少要大于level
			for(j= lastH - 1 ; j >= level; j--) //高度至少大于level
				search(level-1,i,j,leftv - i*i*j, s+2*i*j); 
	}
}

int main(){
	scanf("%d%d",&n,&m);
	int i,j;
	for( i =MAXR; i>0; i--)
		for(j= MAXH; j>0; j--) if( n - i*i*j >= 0)
			search(m-1 , i,j, n - i*i*j , i*i+2*i*j); //第一层，底面积+侧面积
	
	if(INF == ans) //没有可行解
		printf("0\n");
	else	printf("%d\n",ans);
	return 0;
}

• Re:小草的详细注释代码 （大牛不要踩……） (1802) lxfstyle 2011-04-18 13:28:24
  • 那步剪枝真的是很重要 (14) cotton 2011-08-04 09:22:57
• Re:小草的详细注释代码 （大牛不要踩……） (1802) lynu_111 2014-11-26 21:45:35
• Re:小草的详细注释代码 （大牛不要踩……） (1802) 2429586268 2020-03-27 16:21:41