HDU 4359 Easy Tree DP? 组合数学+动归

题意：定义一种树，每个节点的权值都是2到2，每个权值出现一次，每个节点的左子树的权值和小于右子树，除非只有一个子树。给你n和d，问有n个节点且恰好深度是d的这种树有多少种。

比赛的时候我没有做出来，当时A的人还是不少，\

有一个超傻逼的居然没想到，就是  ，这表示一个权值较大的节点是大于所有权值小于他的值之和的。

所以对于每一个合法的树，只要把权值最大的放到右子树就可以满足了。

动归过程:f[i][j]表示i个节点深度不超过j的方案种数。

for (int i = ; i <= N; i++){

        for (int j = ; j <= N; j++){

            f[i][j] = ( * i * f[i - ][j - ]) % MOD;

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

                f[i][j] = (f[i][j] + ((C[i][i - ] * C[i - ][k]) % MOD) * ((f[k][j - ] * f[i - k - ][j - ]) % MOD)) % MOD;

            }

        }

    }

对于根节点分两种情况，只有一个子树，或者左右子树都有。

如果只有一个子树，那么f[i][j] = i * f[i-1][j-1] * 2。 意思就是任取一个节点做根节点，然后把满足条件的f[i-1][j-1]作为根节点的子树，左右两个子树所以再乘以2.

如果左右子树都有，情况稍微麻烦一点，那么就枚举左子树中的节点个数k，1≤k≤i-2，对于每一个k，还是任选一个节点做根节点，然后在除了根节点和剩下的最大值外的i-2个点中选k个到左子树，剩下的自然就到右子树了。这是节点的分配，那方案数呢，左子树有k个节点，深度不超过j-1,就是f[k][j-1]，右子树有i-k-1各节点，深度同样不超过j-1,就是f[i-k-1][j-1]，然后将这些乘起来就得到总的方案数了，所以有了下面总的状态转移方程。

f[i][j] = 2*i*f[i - 1][j - 1] + (i*C[i - 2][k]*f[k][j - 1]*f[i - k - 1][j - 1])(1≤k≤i-2)

其实还是蛮简单的啊，为什么当时不会做呢？？？智商被压制的感觉特别不爽

 #include <iostream>

 #include <cstdio>

 #include <fstream>

 #include <algorithm>

 #include <cmath>

 #include <deque>

 #include <vector>

 #include <queue>

 #include <string>

 #include <cstring>

 #include <map>

 #include <stack>

 #include <set>

 #define LL long long

 #define eps 1e-8

 #define INF 0x3f3f3f3f

 #define OPEN_FILE

 #define MAXN 400

 using namespace std;

 LL f[MAXN][MAXN], C[MAXN][MAXN];

 const LL MOD = 1e9 + ;

 const int N = ;

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     memset(C, , sizeof(C));

     C[][] = ;

     for (int i = ; i <= N; i++){

         C[i][] = ;

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

             C[i][j] = (C[i - ][j - ] + C[i - ][j]) % MOD;

         }

     }

     memset(f, , sizeof(f));

     for (int i = ; i <= N; i++){

         f[][i] = ;

     }

     for (int i = ; i <= N; i++){

         for (int j = ; j <= N; j++){

             f[i][j] = ( * i * f[i - ][j - ]) % MOD;

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

                 f[i][j] = (f[i][j] + ((i * C[i - ][k]) % MOD) * ((f[k][j - ] * f[i - k - ][j - ]) % MOD)) % MOD;

             }

         }

     }

     int T;

     scanf("%d", &T);

     int n, d;

     for (int cas = ; cas <= T; cas++){

         scanf("%d%d", &n, &d);

         printf("Case #%d: %I64d\n", cas, (f[n][d] - f[n][d - ] + MOD) % MOD);

     }

     return ;

 }