长沙理工大学第十二届ACM大赛-重现赛 K - 大家一起来数二叉树吧

题目描述

某一天,Zzq正在上数据结构课。老师在讲台上面讲着二叉树,zzq在下面发着呆。
突然zzq想到一个问题:对于一个n个节点,m个叶子的二叉树,有多少种形态呐?你能告诉他吗?
对于第一组样例的解释
长沙理工大学第十二届ACM大赛-重现赛 K - 大家一起来数二叉树吧
 

输入描述:

每一组输入一行,两个正整数n,m(n<=50)意义如题目

输出描述:

每一行输出一个数,表示相应询问的答案取模1000000007
示例1

输入

4 2
10 5

输出

6
252

备注:

a取模b等于a%b,即a除以b的余数

题解

$dp$。

$dp[i][j]$表示有$i$个节点,$j$个叶子节点的不同二叉树的形态。

对于$dp[i][j]$,我们可以枚举根节点左子树的节点个数$x$和叶子节点个数$y$,将$dp[x][y] * dp[i-1-x][j-y]$累加就可以得到$dp[i][j]$了。

#include <bits/stdc++.h>
using namespace std; long long mod = 1e9 + 7;
long long dp[60][60];
int n, m; int main() {
dp[0][0] = 1;
dp[1][1] = 1;
for(int i = 2; i <= 50; i ++) {
for(int j = 1; j <= i - 1; j ++) {
dp[i][j] = 0;
for(int x = 0; x <= i - 1; x ++) {
for(int y = 0; y <= x; y ++) {
if(j - y < 0) continue;
long long sum = dp[x][y] * dp[i - 1 - x][j - y] % mod;
dp[i][j] = (dp[i][j] + sum) % mod;
}
}
}
}
while(~scanf("%d%d", &n, &m)) {
printf("%lld\n", dp[n][m]);
}
return 0;
}

  

上一篇:Go语言学习之12 etcd、contex、kafka消费实例、logagent


下一篇:windows下mysql配置(第一次)