1470平衡二叉树计数.cpp

自己的ac代码 在acm.zju.edu.cn 上的题目

#include<stdio.h>
#include<string.h>
int opt[9][21][21];
int vec[100][4];
int tot;

int main()
{
	memset(opt,0,sizeof(opt));
	opt[0][0][0]=1;
	int i,j,k,d;
	tot=0;
	int ans[21][21];
	for(d=0;d<=7;d++)
	{
		for(i=0;i<=20;i++)
			for(j=0;j<=20;j++)
			{
				if(opt[d][i][j]!=0)
				{
					tot++;
					vec[tot][0]=opt[d][i][j];
					vec[tot][1]=d;
					vec[tot][2]=i;
					vec[tot][3]=j;
					for(k=1;k<tot;k++)
					{
						if(vec[tot][1]-vec[k][1]==1 ||vec[tot][1]-vec[k][1]==0)
						{
							if(i+vec[k][2]+1<=20 && j+vec[k][3]<=20)
								opt[d+1][i+vec[k][2]+1][j+vec[k][3]]+=2*vec[tot][0]*vec[k][0];
						}
					}
				    if(i+j==0)
						opt[d+1][1][1]+=vec[tot][0]*vec[tot][0];
					else if( 2*i+1<=20 && 2*j<=20)
						opt[d+1][2*i+1][2*j]+=vec[tot][0]*vec[tot][0];
				}
			}
	}

	memset(ans,0,sizeof(ans));
	for(i=1;i<=tot;i++)
	{
		ans[vec[i][2]][vec[i][3]]+=vec[i][0];
	}
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		printf("%d\n",ans[n][m]);
	}
	return 0;
}