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 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include