HDU 4359 Easy Tree DP？（是dp但并不是tree dp + 组合计数）

分类：

HDU 4359

题意：定义Bear Tree为一颗二叉树，这种二叉树每个结点有一个权值，范围在2^0~2^n-1，并且每个值只用一次，对于每个结点，如果同时存在左右子树，那么左子树的权值和要小于右子树的权值和。求点数为N，层次为D的Bear Tree的数量。

思路：

2^0 + 2^1 + … + 2^n < 2^(n+1)

根据这个性质，我们可以得出权值最大节点必须在右子树上，并且只要同时存在左右子树，则将权值最大节点放在右子树上就一定符合条件。

所以我们用dp[i][j]表示点数为i且深度不超过j的所有方案数，那么输出结果就是dp[n][d]-dp[n][d-1]。

而dp[n][d]的构成分下面两种：

1是只有左子树或只有右子树的情况，我们发现，只需要取任意一个节点来做根节点，乘以可能的子树情况（即dp[n-1][d-1]），再区别开是左子树还是右子树，总共有dp[n-1][d-1] * C(n,1) * 2种情况。

2是同时有左右子树的情况，我们假设左子树有k个节点，则有dp[n-k-1][d-1]【右子树】 * dp[k][d-1]【左子树】 * C(n-2,k) 【左子树节点组成】* C(n,1)【根节点选择】

我们把一二相加即可得到转移方程，，值得注意的是，由于n ,k<= 360随时可能爆精度，每次操作都尽可能模除10^9+7.

Code：

/** @author Novicer* language : C++/C*/#include<iostream>#include<sstream>#include<fstream>#include<vector>#include<list>#include<deque>#include<queue>#include<stack>#include<map>#include<set>#include<bitset>#include<algorithm>#include<cstdio>#include<cstdlib>#include<cstring>#include<cctype>#include<cmath>#include<ctime>#include<iomanip>#define INF 2147483647#define cls(x) memset(x,0,sizeof(x))#define rise(i,a,b) for(int i = a ; i <= b ; i++)using namespace std;const double eps(1e-8);typedef long long lint;const int maxn = 365;const int maxd = 365;const lint mod = 1e9 + 7;lint dp[maxn][maxd];lint C[maxn][maxd];void init(){cls(C);memset(dp,-1,sizeof(dp));C[0][0] = 1;for(int i = 1 ; i < maxn ; i++){C[i][0] = 1;for(int j = 1 ; j <= i ; j++){C[i][j] = C[i-1][j-1] + C[i-1][j];//printf("C[%d][%d] : %I64d\n" ,i ,j ,C[i][j]);if(C[i][j] > mod) C[i][j] -= mod;}}}lint f(int n , int d){if(n == 1 && d >= 1) return 1;if(n == 1 || d == 0) return 0;if(dp[n][d] != -1) return dp[n][d];lint &ans = dp[n][d];ans = (f(n-1 , d-1) * C[n][1] * 2) % mod;for(int k = 1 ; k <= n-2 ; k++)ans = (ans + ((( ( (f(n-k-1 , d-1) * f(k , d-1)) % mod) * C[n-2][k]) % mod) * C[n][1]) % mod) % mod;return ans;}int main(){int t ; cin >> t ; int kase = 1;init();while(t–){int n , d;cin >> n >> d;lint ans = f(n,d) – f(n,d-1);ans = (ans + mod) % mod;cout << "Case #" << kase++ << ": " << ans << endl;}return 0;}

上一篇HDU 4355 Party All the Time（三分法搜索）下一篇HDU 4365 Palindrome graph（几何变换+快速幂）

顶0踩0

要知道，当你一直在担心错过了什么的时候，其实你已经错过了旅行的意义。

相关文章：

你感兴趣的文章：

标签云：