4171890_ac_0ms_312k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>

int N, M, S;
int R[22], H[22];
int min[22], minarea[22];

int max(int floor)
{
	int i, r, h, ret;

	r = R[floor+1]-1;
	h = H[floor+1]-1;
	ret = 0;
	for(i = floor; i > 0; i--)
	{
		ret += r*r*h;
		r--;
		h--;
	}
	return ret;
}

int getarea(int floor)
{
	int area = R[M]*R[M];
			
	for(int i = M; i >= floor; i--)
	{
		area += 2*R[i]*H[i];
	}
	return area;
}

void solve(int floor,int nown)
{
	int r, h, tn, ts;

	if(floor==0)
	{
		if(nown==N)
		{
			int area = getarea(1);
			if(S==0||area < S)
			{
				S = area;
			}
		}
		return ;
	}
	for(r = R[floor+1]-1; r >= floor; r--)
	{
		R[floor] = r;
		for(h = H[floor+1]-1; h >= floor; h--)
		{
			H[floor] = h;
			tn = nown + r*r*h;
			if(tn + min[floor-1] > N)
				continue;
			if(tn + max(floor-1) < N)
				continue;
			ts = getarea(floor);
			if(S!=0&&ts+minarea[floor-1]>S)
				continue;
			if(S!=0&&2*(N-tn)>=R[floor]*(S-ts))
				continue;
			solve(floor-1,tn);
		}
	}
}

void init()
{
	int i;

	min[0] = 0;
	minarea[0] = 0;
	for(i = 1; i <= 20; i++)
	{
		min[i] = i*i*i+min[i-1];
		minarea[i] = minarea[i-1]+i*i;
	}
}

int main()
{
	init();
	scanf("%d%d",&N,&M);
	S = 0;
	R[M+1] = (int)sqrt(N)+1;
	H[M+1] = (int)sqrt(N)+1;
	solve(M,0);
	printf("%d\n",S);
	return 0;
}