Cow Pedigrees - USACO 2.3.2

cowpedigrees - codetrick
Farmer John is considering purchasing a new herd of cows. In this new herd, each mother cow gives birth to two children. The relationships among the cows can easily be represented by one or more binary trees with a total of N (3 <= N < 200) nodes. The trees have these properties:

• The degree of each node is 0 or 2. The degree is the count of the node's immediate children.
• The height of the tree is equal to K (1 < K <100). The height is the number of nodes on the longest path from the root to any leaf; a leaf is a node with no children.

How many different possible pedigree structures are there? A pedigree is different if its tree structure differs from that of another pedigree. Output the remainder when the total number of different possible pedigrees is divided by 9901.

PROGRAM NAME: nocows

INPUT FORMAT

• Line 1: Two space-separated integers, N and K.

SAMPLE INPUT (file nocows.in)

5 3    

OUTPUT FORMAT

• Line 1: One single integer number representing the number of possible pedigrees MODULO 9901.

SAMPLE OUTPUT (file nocows.out)

2    OUTPUT DETAILS:

Two possible pedigrees have 5 nodes and height equal to 3:
           @                   @      
          / \                 / \
         @   @      and      @   @
        / \                     / \
       @   @                   @   @

http://zeffsalgo.blogspot.com/2013/12/usaco-training-problem-cow-pedigrees.html

每个树的状态都由其左右子树状态决定,根据乘法原理,其状态数等于左右子树状态数乘积 题目限制了数树的深度

dp[n,k]=∑(dp[n,k-1]*dp[n-1-i,k-1])(i∈1..i-2) 边界条件：dp[1,i]=1

结果就是 dp[N][K]-dp[N][K-1]

http://my.oschina.net/u/347565/blog/63684
        dp[i][j]表示i个结点可以组成的不超过j层的不同二叉树的数量。一共i个结点，除了根结点，还有i-1个结点，左子树m个结点，右子树i-1-m个结点，左子树不超过j-1层的数量dp[m][j-1]，右子树不超过j-1层的数量dp[i-1-m][j-1]，因此dp[i][j]=dp[m][j-1]*dp[i-1-m][j-1]，又因为m的取值为1,2,…,i-2，所以dp[i][j]= dp[1][j-1]*dp[i-2][j-1]+dp[2][j-1]*dp[i-3][j-1]+...+dp[i-2][j-1]*dp[1][j-1]，即dp[i][j]=∑（dp[m][j-1]*dp[i-1-m][j-1]）（m=1,2…,i-2）。

int dp[210][110];

int main()

{

    int n,k;

    cin>>n>>k;

    int i,j,m;

    for(j=0;j<=k;j++)//设置边界条件

        dp[1][j]=1;

    for(j=2;j<=k;++j)

        for(i=2;i<=n;++i)

            for(m=1;m<=i-1;++m)

                dp[i][j]=(dp[i][j]+dp[m][j-1]*dp[i-1-m][j-1])%9901;//递归求解

    cout<<(dp[n][k]-dp[n][k-1]+9901)%9901<<endl;

    return 0;

}

http://dtyfc.com/acmblog/acm/621

int gao(int n, int k) {

    if(n < k) return 0;

    if(~dp[n][k]) return dp[n][k];

    int ans = 0;

    for(int i = 1; i < n; i += 2) {

        for(int j = 1; j < k; j++) {

            if(j != k - 1) ans += 2 * gao(i, k - 1) * gao(n - 1 - i, j);

                else ans += gao(i, k - 1) * gao(n - 1 - i, j);

            ans %= M;

        }

    }

    return dp[n][k] = ans;

}

http://zeffsalgo.blogspot.com/2013/12/usaco-training-problem-cow-pedigrees.html
Read full article from cowpedigrees - codetrick