首页 > 其他 > 详细

UASCO Cow Pedigrees /// oj10140

时间:2018-05-17 23:53:02      阅读:49      评论:0      收藏:0      [点我收藏+]

标签:ace   def   its   bits   while   b-   cow   name   mem   

题目大意:

输入n,m ;二叉树

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

Sample Input

5 3

Sample Output

2

即 两个方案为
         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[210][110];
int main() {
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        memset(dp,0,sizeof(dp));
        for(int j=1;j<=m;j++)
            for(int i=1;i<=n;i+=2)
            {
                if(i==1) dp[i][j]=1;
                for(int k=1;k<=i-2;k+=2)
                    dp[i][j]=(dp[i][j]+dp[i-1-k][j-1]*dp[k][j-1])%MOD;
            }
        printf("%d\n",(dp[n][m]-dp[n][m-1]+MOD)%MOD);
    }
    return 0;
}
View Code

 

UASCO Cow Pedigrees /// oj10140

标签:ace   def   its   bits   while   b-   cow   name   mem   

原文:https://www.cnblogs.com/zquzjx/p/9053750.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号