3733560_ac_0ms_212k.cpp

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

#include <stdio.h>
#include <string.h>

__int64 num[19][201];
int maxi[19];

void dp()
{
	int i, j, k;

	maxi[1] = 0;
	for (i = 2; i < 19; i++)
	{
		maxi[i] = maxi[i - 1] + i - 1;
	}
	memset(num, 0, sizeof(num));
	num[2][0] = 1;num[2][1] = 1;
	for (i = 3; i < 19; i++)
	{
		num[i][0] = 1;
		for (j = 1; j < maxi[i]; j++)
		{
			num[i][j] = 0;
			for (k = 1; k <= i && j >= k - 1; k++)
			{
				num[i][j] += num[i - 1][j - k + 1];
			}
		}
		num[i][maxi[i]] = 1;
	}
}

void go()
{
	int i, k;

	while (scanf("%d%d", &i, &k) == 2)
	{
		if (i == 0 && k == 0)
		{
			break;
		}
		printf("%I64d\n", num[i][k]);
	}
}

int main()
{
	dp();
	go();
	return 0;
}