pku1190.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

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

int N, M;
int min;
int V[21], S[21];

void Search(int lv, int ns, int sr, int sh, int nlev)
{
	int i, j, th, maxh;

	if (lv < V[nlev] || ns + S[nlev] >= min)
		return;
	if (nlev == 0)
	{
		if (lv == 0 && min > ns)
			min = ns;
		return;
	}
	for (i = sr; i >= nlev; i--)
	{
		th = (int)((lv - V[nlev - 1]) / (double)(i * i));
		maxh = th < sh ? th : sh;
		if (nlev == M)
			ns = i * i;
		for (j = maxh; j >= nlev; j--)
		{
			if (2 * (lv - i * i * j) / i + ns + 2 * i * j >= min) continue;
			Search(lv - i * i * j, ns + 2 * i * j, i - 1, j - 1, nlev - 1);
		}
	}
}

void Solve()
{
	min = 0x7fffffff;
	Search(N, 0, (int)sqrt(N * 1.0 / M), (int)(N * 1.0 / M / M), M);
	printf("%d\n", min == 0x7fffffff ? 0 : min);
}

int pre()
{
	int i;
	V[0] = 0;
	S[0] = 0;
	for (i = 1; i < 21; i++)
	{
		V[i] = V[i - 1] + i * i * i;
		S[i] = S[i - 1] + i * i * 2;
	}
}

int main()
{
	pre();
	while (EOF != scanf("%d %d", &N, &M))
		Solve();
	return 0;
}