BZOJ3769:BST again(记忆化搜索DP)

Description

求有多少棵大小为n的深度为h的二叉树。（树根深度为0；左右子树有别；答案对1000000007取模）

Input

第一行一个整数T，表示数据组数。

以下T行，每行2个整数n和h。

Output

共T行，每行一个整数表示答案（对1000000007取模）

Sample Input

2
2 1
3 2

Sample Output

2
4

HINT

对于100%的数据，1<=n<=600,0<=h<=600,1<=T<=10

Solution

$f[i][j]$表示树大小为$i$，最深深度小于等于$j$的二叉树数量。

$f[i][j]=sum_{k=1}^{i}f[k-1][j-1]*f[i-k][j-1]$

多组数据用记搜

Code

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #define N (609)
 5 #define MOD (1000000007)
 6 using namespace std;
 7 
 8 int T,n,h,f[N][N],ans;
 9 
10 int DP(int sz,int hi)
11 {
12     if (sz==0) return 1;
13     if (hi==0) return sz==1;
14     if (f[sz][hi]!=-1) return f[sz][hi];
15     f[sz][hi]=0;
16     for (int i=1; i<=sz; ++i)
17         (f[sz][hi]+=1ll*DP(i-1,hi-1)*DP(sz-i,hi-1)%MOD)%=MOD;
18     return f[sz][hi];
19 }
20 
21 int main()
22 {
23     memset(f,-1,sizeof(f));
24     scanf("%d",&T);
25     while (T--)
26     {
27         scanf("%d%d",&n,&h);
28         ans=DP(n,h);
29         if (h>0) ans-=DP(n,h-1);
30         printf("%d
",(ans%MOD+MOD)%MOD);
31     }
32 }