USACO-2.3Cow Pedigrees+DP

令dp[i][j]表示i个节点构成高度不大于j的树的方法数。如果我们将给定的树去掉根节点，那么这棵树就可以分成独立的左右两棵子树，然后如果左子树具有a中形态，右子树具有b中形态，那么这棵树总共有a*b种形态。
所以我们得到状态转移方程dp[i][j]=dp[k][j-1]*dp[i-k-1][j-1].其中k可以看成是在穷举左子树中含有的节点数为k个。边界条件是dp[1][1,k]=1;

代码如下：

/*
ID:15674811
LANG:C++
PROG:nocows
*/

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<fstream>
using namespace std;

#define mod 9901
int main()
{
    ofstream fout("nocows.out");
    ifstream fin("nocows.in");
    //ifstream fin("lkl.txt");
    int dp[220][110];
    int n,k;
    while(fin>>n>>k)
    {
         memset(dp,0,sizeof(dp));
         for(int i=1;i<=k;i++)
             dp[1][i]=1;
         for(int i=2;i<=n;i++)
            for(int j=1;j<=k;j++)
            {
                for(int d=1;d<=i-2;d++)
                {
                    dp[i][j]=(dp[i][j]+dp[d][j-1]*dp[i-d-1][j-1])%mod;
                }
            }
          ///mod以后有可能dp[n][k]小于dp[n][k-1]
         ///相减有可能出现负值所加上一个mod
         int ans=(dp[n][k]-dp[n][k-1]+mod)%mod;
         fout<<ans<<endl;
    }
  return 0;
}