Easy Tree DP?
http://acm.hdu.edu.cn/showproblem.php?pid=4359
Problem Description
A Bear tree is a binary tree with such properties : each node has a value of 20,21…2(N-1)(each number used only once),and for each node ,its left subtree’s elements’ sum<its right subtree’s elements’ sum(if the node hasn’t left/right
subtree ,this limitation is invalid).
You need to calculate how many Bear trees with N nodes and exactly D deeps.
subtree ,this limitation is invalid).
You need to calculate how many Bear trees with N nodes and exactly D deeps.
Input
First a integer T(T<=5000),then T lines follow ,every line has two positive integer N,D.(1<=D<=N<=360).
Output
For each test case, print "Case #t:" first, in which t is the number of the test case starting from 1 and the number of Bear tree.(mod 109+7)
Sample Input
2 2 2 4 3
Sample Output
Case #1: 4 Case #2: 72
题意：给你N(0~N-1)个结点，结点的权值为2^(i -1)，问用N个结点能形成多少种高度为D的树，要求树的结点如果同时有左右子树，左子树的和必须小于右子树。
题解：因为结点的权值为2^(i-1)的形式，所以如果有左右子树，只要把剩下的结点中的最大的放入右子树即可满足条件。写出有左右子树和只有一个子树的两种情况的状态转移就行了。
#include<cstdio>
#include<cstring>
using namespace std;
#define LL long long
#define MAX 365
#define mod 1000000007
LL dp[MAX][MAX];//i个点不超过j深度的组合数
//dp[i][j]=2*c[i][i-1]*dp[i-1][j-1]+c[i][i-1]*c[i-2][k]*dp[k][j-1]*dp[i-1-k][j-1](1<=k<=i-2)
LL comb[MAX][MAX];//组合数
void init()
{
memset(dp,0,sizeof(dp));
for(int i=0;i<=360;++i)
comb[i][0]=comb[i][i]=1;
for(int i=2;i<=360;++i)
for(int j=1;j<=i;++j)
comb[i][j]=(comb[i-1][j]+comb[i-1][j-1])%mod;
}
void cal()
{
for(int i=1;i<=360;++i)
dp[1][i]=1;
for(int j=2;j<=360;++j)
for(int i=2;i<=360;++i)
{
dp[i][j]=(dp[i][j]+2*comb[i][i-1]*dp[i-1][j-1])%mod;//只有左子树或右子树
for(int k=1;k<=i-2;++k)
dp[i][j]=(dp[i][j]+((comb[i][1]*comb[i-2][k])%mod)*((dp[k][j-1]*dp[i-1-k][j-1])%mod))%mod;
}
}
int main()
{
int n,m,T;
scanf("%d",&T);
init();
cal();
for(int cas=1;cas<=T;++cas)
{
printf("Case #%d: ",cas);
scanf("%d%d",&n,&m);
printf("%d\n",(dp[n][m]+mod-dp[n][m-1])%mod);
}
return 0;
}