【NOIP2016DP专题测试】圣主的考验

发布于 2016-11-15  510 次阅读


题目大意:给定节点数N,求出由N个节点构成的二叉树对于任意一个节点都满足其|左子树高度-右子树高度|<=1的树的形态总数。


题目分析:设计状态f[i][j]表示由i个节点,层高为j的二叉树的形态个数,那么我们枚举左子树和右子树的形态,即可得出方程:f[i][j]+=f[k][j-1]*f[i-k-1][j-1]+f[k][j-1]*f[i-k-1][j-2]+f[k][j-2]*f[i-k-1][j-1]。

同时用l[i]和r[i]分别表示其子树可行的范围。

先预处理然后O(1)输出即可。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<queue>
#include<cassert>
#include<climits>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
typedef long long LL;
const int mod=1e9;
int f[3005][3005],ans[3005],n,l[3005],r[3005];

int main(){
	f[0][0]=ans[0]=1;
	For (i,3000){
		Rep (j,i)
			Fork (k,l[j],r[j]){
				f[i][k+1]=(f[i][k+1]+1LL*f[j][k]*f[i-j-1][k])%mod;
				if (k) f[i][k+1]=(f[i][k+1]+1LL*f[j][k]*f[i-j-1][k-1])%mod;
				f[i][k+2]=(f[i][k+2]+1LL*f[j][k]*f[i-j-1][k+1])%mod;
			}
		For (j,i){
			if (f[i][j]) {
				l[i]=j;break;
			}
		}
		ForD (j,i){
			if (f[i][j]){
				r[i]=j;break;
			}
		}
		Fork (j,l[i],r[i])
			(ans[i]+=f[i][j])%=mod;
	}
	while (1){
		scanf("%d",&n);
		if (!n) return 0;
		if (n<37) printf("%d\n",ans[n]);else printf("%.9d\n",ans[n]);
	}
} 

「知我罪我,其惟春秋」