HDU 4359——Easy Tree DP?——————【dp+组合计数】

Easy Tree DP?

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1460 Accepted Submission(s): 557

Problem Description

A Bear tree is a binary tree with such properties : each node has a value of 2⁰,2¹…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.

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 10⁹+7)

Sample Input

2 2

4 3

Sample Output

Case #1: 4

Case #2: 72

Author

smxrwzdx@UESTC_Brightroar

Source

2012 Multi-University Training Contest 6

题目大意：定义bear树是一棵二叉树。如果有左右子树，那么需要满足左子树的所有结点值总和小于右子树的所有结点值总和。每个结点的值都在2⁰,2¹…2^{(N-1)中，这n个数只能被选一次。问你有多少种符合的方案。}

^{解题思路：首先定义dp[i][j]表示有i个结点时，树深不超过j的方案数。我们发现根结点是可以选任意值的。然后剩下的可以分情况考虑。首先考虑只有左子树或者右子树，那么剩下的i-1个结点就构成了只有左或右子树的情况，即dp[i-1][j-1]*2*i。然后考虑同时有左右子树的情况，我们在根结点放任意值，然后将i-1个值分到左右子树中，因为只要右子树中有一个剩下的i-1个值中的最大值那么就能满足要求。那么我们可以枚举k，让左子树从i-2个值中选k个，即i*C(i-2,k)*dp[k][j-1]*dp[i-1-k][j-1]。综上：可以得到dp转移方程：dp[i][j]=i*dp[i-1][j-1]*2+i*C(i-2,k)*dp[k][j-1]*dp[i-1-k][j-1]。}

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef __int64 INT;
const int MOD=1e9+7;
const int N=361;
INT C[400][400],dp[400][400];
//dp[i][j]表示有i个结点，树深不超过j的方案数
void getC(){    //得到组合数
    memset(C,0,sizeof(C));
    C[0][0]=1;
    for(int i=1;i<=N;i++){
        C[i][0]=C[i][i]= 1;
        for(int j=1;j<i;j++){
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
        }
    }
}
void getdp(){
    memset(dp,0,sizeof(dp));
    for(int i=0;i<=N;i++)   //看做空树的情况
        dp[0][i]=1;
    for(int i=1;i<=N;i++)   //看做只有一个根结点的树的情况
        dp[1][i]=1;
    for(int i=2;i<=N;i++){
        for(int j=1;j<=N;j++){
            dp[i][j]=((2*C[i][i-1])%MOD*dp[i-1][j-1])%MOD;  //只有左或右子树的情况
            for(int k=1;k<=i-2;k++){
            //同时有左右子树的情况，根结点随意取，右子树中需要含有剩余的i-1个数中的最大值
                dp[i][j]+=((C[i][i-1]*C[i-2][k])%MOD*(dp[k][j-1]*dp[i-k-1][j-1]%MOD))%MOD;
                dp[i][j]%=MOD;
            }
        }
    }
}
int main(){
    getC();
    getdp();
    int t,n,d,cnt=0;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&d);
        //根据dp的定义，那么应将有n个结点，树深小于等于d-1的情况去掉才是树深为d的所有情况。题解说反复取模后dp[n][d]的值可能小于dp[n][d-1]。
        printf("Case #%d: %I64d
",++cnt,((dp[n][d]-dp[n][d-1])%MOD+MOD)%MOD);
    }
    return 0;
}