Cow Pedigrees（DP）

Cow Pedigrees

Silviu Ganceanu -- 2003

 

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      @   @
        / \                     / \
       @   @                   @   @

 

   题意：

   给出 N（3 ~ 200）和 K（1 ~ 100），代表有 N 个结点，K 的深度。输出能有多少种满足 N 结点，K 深度的二叉树形态。结果要MODULO 9901。

 

   思路：

   DP。

   dp [ i ][ j ] 代表 i 节点 j - 1 深度的二叉树种数。small [ i ] [ j ] 代表 i 节点下小于等于 j 深度的种数有多少种。一颗二叉树可以由一个节点 + 两颗子树（左右子树）构成，那么 K 深度是由 K - 1深度来的，并且给出的结点一定会是奇数。故可以dp [ i ][ j ] 可以分成 3 种情况讨论：

   设左子树节点数为 p ，那么右子树节点数则为 N - p - 1；

   1.dp[ i ][ j ] += dp[ p ][ j - 1] + small[ N - p - 1 ][ j - 2];    由左子树深度为 j - 1，右子树深度小于 j - 1（即小于等于j - 2的）来构成；

   2.dp[ i ][ j ] += small[ p ][ j - 2] + dp[ N - p - 1 ][ j - 1];    由左子树深度小于 j - 1（即小于等于j - 2的），右子树深度为 j - 1 来构成；

   3.dp[ i ][ j ] += dp[ p ][ j - 1] + dp[ N - p - 1 ][ j - 1];        由左右子树深度都为 j - 1 深度来构成。

   

   AC：

/*
TASK:nocows
LANG:C++
ID:sum-g1
*/
#include<stdio.h>
#include<string.h>
int dp[205][105];
int small[205][105];

int main()
{
    freopen("nocows.in","r",stdin);
    freopen("nocows.out","w",stdout);
    int n,k;
    scanf("%d%d",&n,&k);
    memset(dp,0,sizeof(dp));
    dp[1][1] = 1;
    for(int i = 1;i <= k;i++)
        small[1][i] = 1;
    for(int i = 3;i <= n;i += 2)
    {
        for(int j = 2;j <= k;j++)
        {
            for(int l = 1;l < i;l += 2)
            {
                dp[i][j] += (dp[l][j - 1] * small[i - l - 1][j - 2] % 9901);
                dp[i][j] += (small[l][j - 2] * dp[i - l - 1][j - 1] % 9901);
                dp[i][j] += (dp[l][j - 1] * dp[i - l - 1][j - 1] % 9901);
            }
            dp[i][j] %= 9901;
            for(int l = j;l <= k;l++)
                small[i][l] += dp[i][j];
        }
    }
    printf("%d\n",dp[n][k]);
    return 0;
}