题目链接：USACO-Cow Pedigrees
dp[i][j]表示深度为i，点数为j的树的种类，small[i][j]表示深度小于i，点数为j的树的种类。 状态转移方程为dp[i][j]=dp[i-1][1~j]*dp[i-1][j~1]+dp[i-1][1~j]*small[i-1][1~j]+small[i-1][j~1]*dp[i-1][j~1]
/* ID: xdujlx1 PROG: nocows LANG: C++ */ #include<bits/stdc++.h> using namespace std; int dp[107][207],small[107][207]; const int mod=9901; void ioinit() { freopen("nocows.in","r",stdin); freopen("nocows.out","w",stdout); } int main() { ioinit(); int n,k; scanf("%d%d",&n,&k); dp[1][1]=1; small[2][1]=1; for(int i=2;i<=k;i++) { for(int j=1;j<=n;j+=2) { small[i+1][j]=small[i][j]; for(int p=1;p<j;p+=2) { dp[i][j]=(dp[i][j]+dp[i-1][p]*dp[i-1][j-p-1])%mod; dp[i][j]=(dp[i][j]+small[i-1][p]*dp[i-1][j-p-1])%mod; dp[i][j]=(dp[i][j]+dp[i-1][p]*small[i-1][j-p-1])%mod; } small[i+1][j]=(small[i+1][j]+dp[i][j])%mod; } } printf("%d\n",dp[k][n]); return 0; }