USACO Section 2.3 Cow Pedigrees

本文主要是介绍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 %d\n",i,j,dp[i][j]);}}printf("%d\n",(dp[n][h]-dp[n][h-1]+9901)%9901);return 0;
}

这篇关于USACO Section 2.3 Cow Pedigrees的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---