3054669_wa.cc

来自「北大大牛代码 1240道题的原代码 超级权威」· CC 代码 · 共 42 行

#include <stdio.h>

int n[490], l, f[42770];

void init()
{
	int i;

	l = 0;
	for(i = 1; i*i < 32768; i++)
	{
		n[l++] = i*i;
	}
}

void dp()
{
	int i, j;

	f[1] = 1;
	for(i = 2; i < 32769; i++)
	{
		f[i] = 0;
		for(j = 0; n[j] < i; j++)
		{
			f[i] += f[i-n[j]];
		}
	}
}

int main()
{
	int num;

	init();
	dp();
	while(scanf("%d",&num),num)
	{
		printf("%d\n",f[num]);
	}
	return 0;
}