Codeforces 9D How many trees? 【计数类DP】

Codeforces 9D How many trees?

LINK

题目大意就是给你一个n和一个h

问你有多少个n个节点高度不小于h的二叉树

n和h的范围都很小

感觉有无限可能

考虑一下一个很显然的DP

$dp_{n,h}表示n个节点组成的高度为h的树的方案数$

然后考虑咋转移

首先我们可以肆无忌惮地，枚举一下，因为左右子树的高度至少有一个是h-1，所以我们需要枚举一个子树的大小和另一个子树的高，但是我们发现，当左右两个子树的高度相等的时候贡献会统计两次，减掉一次贡献就行了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 50
 4 #define LL long long
 5 #define fu(a,b,c) for(int a=b;a<=c;++a)
 6 #define fd(a,b,c) for(int a=b;a>=c;--a)
 7 LL dp[N][N];
 8 int n,h;
 9 int main(){
10     scanf("%d%d",&n,&h);
11     dp[0][0]=1;
12     fu(i,1,n)
13         fu(j,0,n)
14             fu(k,0,j-1){
15                 fu(p,0,i-1)dp[i][j]+=2ll*dp[i-1][k]*dp[p][j-k-1];
16                 dp[i][j]-=dp[i-1][k]*dp[i-1][j-k-1];
17             }
18     LL ans=0;
19     fu(i,h,n)ans+=dp[i][n];
20     printf("%lld",ans);
21     return 0;
22 }