【BZOJ3769】BST again [DP]

BST again

Time Limit: 10 Sec Memory Limit: 256 MB
[Submit][Status][Discuss]

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

　　1<=n<=600,0<=h<=600,1<=T<=10

Solution

　　我们运用DP来求解。

　　记f[i][j]表示点数为i，深度==j的方案数；
　　记g[i][j]表示点数为i，深度<=j的方案数。

　　转移的时候所以枚举一个点k作为根，那么左边显然就有k-1个点，右边就有i-k个点。

　　此时深度恰好为j-1的方案数为：
　　g[k-1][j-1] * g[i-k][j-1] - g[k-1][j-2] * g[i-k][j-2]。

　　所以我们就可以得到答案了。

Code

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 using namespace std;

 typedef long long s64;

 const int ONE = ;

 const int MOD = 1e9 + ;

 int T;

 int n, h;

 int x, y;

 int f[ONE][ONE], g[ONE][ONE];

 struct pwoer

 {

         int x, y;

 }a[ONE];

 int get()

 {

         int res=,Q=;  char c;

         while( (c=getchar())< || c>)

         if(c=='-')Q=-;

         if(Q) res=c-;

         while((c=getchar())>= && c<=)

         res=res*+c-;

         return res*Q;

 }

 void Modit(int &a)

 {

         if(a < ) a += MOD;

         if(a >= MOD) a -= MOD;

 }

 int main()

 {

         T = get();

         for(int i = ; i <= T; i++)

             a[i].x = get(), a[i].y = get() + ,

             n = max(n, a[i].x), h = max(h, a[i].y);

         f[][] = ; for(int i = ; i <= h; i++) g[][i] = ;

         f[][] = ; for(int i = ; i <= h; i++) g[][i] = ;

         for(int i = ; i <= n; i++)

         {

             for(int j = ; j <= i; j++)

                 for(int k = ; k <= i; k++)

                     Modit(f[i][j] += (s64)g[k - ][j - ] * g[i - k][j - ] % MOD - (s64)g[k - ][j - ] * g[i - k][j - ] % MOD);

             g[i][] = f[i][];

             for(int j = ; j <= h; j++)

                 Modit(g[i][j] = g[i][j - ] + f[i][j]);

         }    m

         for(int i = ; i <= T; i++)

             printf("%d\n", f[a[i].x][a[i].y]);

 }

巴特西