首页 > 代码库 > [2017浙工大之江学院决赛 M] qwb与二叉树（记忆化搜索，卡特兰数）

[2017浙工大之江学院决赛 M] qwb与二叉树（记忆化搜索，卡特兰数）

2024-09-30 04:14:39   220人阅读

题目链接：http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=12

题意：中文题面。

假如不限定叶子数的话，问题就是求二叉树形态数，可以每次枚举节点数，以后来的节点为根，左右子树的形态数做乘法原理得到，就是卡特兰数。

这里多限定了叶子数，其实没有什么区别，在枚举的时候，左右子树再分别统计一下不同叶子数的情况就行。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const LL mod = 1e9+7;
 6 const int maxn = 55;
 7 LL dp[maxn][maxn];
 8 LL n, m;
 9 
10 LL dfs(int x, int y) {
11     if(y > x) return 0;
12     if(~dp[x][y]) return dp[x][y];
13     LL ret = 0;
14     for(int i = 0; i < x; i++) {
15         for(int j = 0; j <= y; j++) {
16             ret = (ret + (dfs(i, j) * dfs(x-i-1, y-j)) % mod) % mod;
17         }
18     }
19     return dp[x][y] = ret;
20 }
21 
22 int main() {
23     // freopen("in", "r", stdin);
24     memset(dp, -1, sizeof(dp));
25     dp[0][0] = 1; dp[1][0] = 0; dp[1][1] = 1;
26     while(~scanf("%lld%lld",&n,&m)) {
27         printf("%lld\n", dfs(n, m));
28     }
29     return 0;
30 }

 

[2017浙工大之江学院决赛 M] qwb与二叉树（记忆化搜索，卡特兰数）


联系
我们