UASCO Cow Pedigrees /// oj10140

题目大意：

输入n，m ；二叉树

输出 n个点分为m层的方案数；每个点的分支要么是0要么是2

Sample Input

5 3

Sample Output

即两个方案为

O O

/ \ / \

O O 和 O O

/ \ / \

O O O O

关于 dp[ i ][ j ] = dp[ i ][ j ] + dp[ i-1-k ][ j-1 ] * dp[ k ][ j-1 ]

可以这样理解，i 个点分为 j 层时

先取出一个点做根节点为第一层剩下 i-1 个点则分为左右两大支

则此时 i-1 个点被分为两大支，且每支应分为 j-1 层

则（i-1-k 分为 j-1 层的方案）*（k 分为 j-1 层的方案）= i 分为 j 层的方案

#include <bits/stdc++.h>

#define MOD 9901

using namespace std;

int dp[][];

int main() {

    int n,m;

    while(~scanf("%d%d",&n,&m))

    {

        memset(dp,,sizeof(dp));

        for(int j=;j<=m;j++)

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

            {

                if(i==) dp[i][j]=;

                for(int k=;k<=i-;k+=)

                    dp[i][j]=(dp[i][j]+dp[i--k][j-]*dp[k][j-])%MOD;

            }

        printf("%d\n",(dp[n][m]-dp[n][m-]+MOD)%MOD);

    }

    return ;

}

巴特西

UASCO Cow Pedigrees /// oj10140

最新文章

热门文章