3183360_wa.c

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

#include <stdio.h>

int N, S, M;
int R[21], H[21];

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

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

int area(int floor)
{
	int i, ret;

	ret = 0;
//	ret = R[floor]*R[floor];
	for(i = 1; i <= floor; i++)
	{
		ret += 2*R[i]*H[i];
	}
	return ret;
}

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

	if(floor == M+1)
	{
		if(n == N)
		{
			s = area(M);
			if(S==0||s < S)
			{
				S = s;
			}
		}
		return ;
	}
	for(r = R[floor-1]+1; n+r*r*(H[floor-1]+1) <= N; r++)
	{
		R[floor] = r;
		for(h = H[floor-1]+1; n+r*r*h <= N; h++)
		{
			H[floor] = h;
			tn = n + r*r*h;
			ts = area(floor);
			if(S!=0&&ts >= S)
				//return ;
				break;
			if(S!=0&&(2*(N-tn)>=(S-ts)*R[floor]))
				break;
			if(tn + min(floor+1) > N)
				//return ;
				break;
			solve(floor+1,tn);
		}
	}
}

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