1987924_ac_170ms_7912k.c

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

# include <stdio.h>
# define max(a,b) a>b?a:b

int a[1002][102][20];

void add(int m, int n, int x, int y)
{
	int l1, l2, w, i, l;

	w = 0;
	l1 = a[m][n][0];l2 = a[x][y][0];
	l = max(l1,l2);
	for(i = 1; i <= l; i++)
	{
		if(i > l1)
			a[m][n][i] = 0;
		if(i > l2)
			a[x][y][i] = 0;
		a[m][n][i]+=a[x][y][i]+w;
		w = a[m][n][i]/100;
		if(a[m][n][i]>=100)
			a[m][n][i]%=100;
	}
	if(w)
		a[m][n][++l] = w;
	a[m][n][0] = l;
}

int main()
{
	int i, j, m, N, K;
	
	scanf("%d%d",&N,&K);
	if(N < K)
		K = N;
	a[0][0][0] = a[0][0][1] = 1;
	for(i = 1; i <= N; i++)
		for(j = 1; j <= K; j++)
		{
			if(j==1)
			{
				a[i][j][0] = a[i][j][1] = 1;
				continue;
			}
			if(i < j)
				break;
			m = j;
			add(i,j,i,j-1);
			if(i-j<m)
				m = i-j;
			if(i-j)
				add(i,j,i-j,m);
			else
				add(i,j,0,0);
		}
	printf("%d",a[N][K][a[N][K][0]]);
	for(i = a[N][K][0]-1; i > 0; i--)
		printf("%02d",a[N][K][i]);
	printf("\n");
	return 1;
}