hdu 4359 Easy Tree DP? （ dp ）

http://acm.hdu.edu.cn/showproblem.php?pid=4359

好纠结的一道dp 题啊，比赛是倍他的 2 的所烧次方迷惑住了，没想出来
看了解题报告，才知道，用dp 那样做。。。，自己还是很弱啊，想不出来

通过此题我对dp 又有了更多的了解

题目大意：

给你n个节点，第i个节点的权值为2^(i-1)，求满足以下条件的深度为d的二叉树的个数(最后结果对maxmod=109+7取余)：左子树权值之和小于右子树权值之和，当只有一个子树时可以不满足这个条件。

5000个测试点，n,d<=360

题解：

1.首先注意f[n][d]的结果是一定的，所以先预处理出来所有的f[n][d]。然后对每个测试点直接输出f[n][d]即可。

2.由于2^i的特殊性质，题目中有一个条件可以转化：左子树和<右子树和等价于左子树最大值<右子树最大值。

3.f[i][j]表示i个节点组成深度不超过j的满足条件的二叉树个数，则最后答案是(f[n][d]+maxmod-f[n][d-1])%maxmod。（注意在反复取余后最后结果f[n][d]可能会小于f[n][d-1]）

先考虑只有一个子树的情况：（c[i][j]表示组合数）

个数为c[i][i-1]*2*f[i-1][j-1]，其中c[i][i-1]表示选择i-1个节点做子树

在考虑有两个子树的情况

个数为c[i][i-1]*c[i-2][k]*f[k][j-1]*f[i-1-k][j-1]（1<=k<=i-2），其中c[i][j-1]表示选择i-1个节点做子树。由于要满足左子树最大值<右子树最大值，所以选择的i-1个节点中最大的那个一定分配给右子树，所以左子树只能从i-2个节点中选k个做其节点，于是有c[i-2][k]。

综上，f[i][j]=c[i][i-1]*2*f[i-1][j-1]+c[i][i-1]*c[i-2][k]*f[k][j-1]*f[i-1-k][j-1]（1<=k<=i-2)。

*/

View Code

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<set>
 8 #include<map>
 9 #define Min(a,b)  a>b?b:a
10 #define Max(a,b)  a>b?a:b
11 #define CL(a,num)  memset(a,num,sizeof(a));
12 #define inf 9999999
13 #define maxn 400
14 #define mod (1000000000 + 7)
15 #define eps  1e-6
16 #define ll long long
17 using namespace std;
18 long long  f[maxn][maxn],c[maxn][maxn];
19 void init()
20 {
21 
22     CL(c,0);
23     CL(f,0);
24      int i,j;
25       for( i = 0; i <= 360 ; i++)
26       {
27 
28           c[i][0] = 1;
29       }
30       c[0][0] = 1;
31 
32       for( i = 1; i <= 360 ; ++i)
33       {
34           for( j = 1 ; j <= i ; ++j)
35           {
36               c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
37           }
38       }
39 
40 
41 
42 
43 }
44 int main()
45 {
46     int i ,j,k,n,d;
47 
48     init();
49 
50 
51         for( i = 1 ; i <= 360 ; ++i)
52         {
53 
54             f[1][i] = 1;
55         }
56 
57 
58 
59 
60      for( i = 2 ; i <= 360; ++i)
61      {
62          for(j = 1 ;  j <= 360 ;++j)
63          {
64 
65              f[i][j] = (c[i][i - 1]*f[i - 1][j - 1]*2)% mod;
66              for( k = 1 ; k <= i - 2; ++k)
67              {
68 
69                  f[i][j] = ((((c[i][i - 1]*c[i - 2][k]) % mod)*(f[k][j - 1]*f[i - 1 - k][j - 1] % mod) )%mod + f[i][j]) % mod;
70              }
71          }
72      }
73      int t,cas = 0;
74 
75      scanf("%d",&t);
76      while(t--)
77      {
78          scanf("%d%d",&n,&d);
79          printf("Case #%d: %I64d\n",++cas,(f[n][d] - f[n][d - 1] + mod)%mod);
80 
81      }
82 
83 
84 }