USACO Section 2.3 Cow Pedigrees

题意：

N个节点 深度为K 的正则二叉树 求 树有几种形态

思路：

一开始以为是数学题… 看了byvoid的题解才知道是dp…

每棵树由根节点、左子树、右子树构成 由此得状态转移 树=左子树*右子树

节点数和深度是影响答案的属性 所以令dp[i][j]表示i个节点深度在j以内的树的形态数

深度在j以内的树又两个深度在j-1以内的树和一个根节点构成

设左子树k个节点 则状态转移可表示为 dp[i][j] = sum( dp[k][j-1] * dp[i-k-1][j-1] ) (k=1…i-2)

代码：

/*
ID: housera1
PROG: nocows
LANG: C++
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,h;
int dp[210][110];

int main(){
	int Debug=0;
	if(!Debug){
		freopen("nocows.in","r",stdin);
		freopen("nocows.out","w",stdout);
	}
	int i,j,k;
	scanf("%d%d",&n,&h);
	for(i=1;i<=h;i++) dp[1][i]=1;
	for(j=1;j<=h;j++)
	{
		for(i=1;i<=n;i++)
		{
			for(k=1;k<i-1;k++)
			{
				dp[i][j]=(dp[i][j]+dp[k][j-1]*dp[i-k-1][j-1])%9901;
			}
			//printf("%d nodes %d floor %dn",i,dp[i][j]);
		}
	}
	printf("%dn",(dp[n][h]-dp[n][h-1]+9901)%9901);
	return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!