【BZOJ3769】spoj 8549 BST again DP（记忆化搜索?）

时间：2022-02-20 14:32:41

【BZOJ3769】spoj 8549 BST again

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

题解：直接列DP方程，设f[i][j]表示有i个节点，深度为j的二叉树个数，然后列出方程用前缀和优化转移即可（注意防重）。

然后光荣TLE了，正解貌似是记忆化搜索？不过懒得改了，卡了卡常数就过了。

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

typedef long long ll;

const int P=1000000007;

int n,m;

int a[15],b[15];

int f[610][610],s[610][610];

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

void init()

{

	register int i,j,k;

	f[0][0]=s[0][0]=1;

	for(j=1;j<=m;j++)	s[0][j]=1;

	for(i=1;i<=n;i++)	for(j=1;j<=m;j++)

	{

		if(i>=j)	for(k=0;k<i;k++)	f[i][j]=(f[i][j]+(ll)f[k][j-1]*s[i-k-1][j-1]+(ll)s[k][j-2]*f[i-k-1][j-1])%P;

		s[i][j]=(s[i][j-1]+f[i][j])%P;

	}

}

int main()

{

	int i,T=rd();

	for(i=1;i<=T;i++)	a[i]=rd(),b[i]=rd()+1,n=max(n,a[i]),m=max(m,b[i]);

	init();

	for(i=1;i<=T;i++)	printf("%d\n",f[a[i]][b[i]]);

	return 0;

}

相关文章