盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码
  5. 更新日志

HDU 5103 RootedTree(状压dp, 树dp)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5103

题意

有一棵树,给定n个节点,问有多少颗有根树,使得每个子树都满足以下条件:子树的根为i,子树上的点数为ti,li<=ti<=ri

思路

dp[i][S] 表示以i为根节点,拥有孩子S(二进制数状态的方案数
sub[S] 表示S状态下森林的方案数
sum[S] 表示S状态的有根树的方案数

可以知道
dp[i][S] = sub[ S^(1<<i) ] {L[i]<=|S|<=R[i]}
sum[S] = dp[i][S] { i=0,1,2,3,,,n-1 | S&1<<i!=0 }
sub[S] = sub[S] + sum[H]*sub[S^H]{ H为s的子集 ,这里有可能会计算重复,所以先固定S中的某一个点一定在H中,这样可以避免重复计算}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define INF 1 << 30
#define fi first
#define se second
#define debug puts("=====================");
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
ll dp[15][1 << 15], sum[1 << 15], sub[1 << 15];
int l[15], r[15], n;
int cal(int s) {
int res = 0;
for (int i = 0; i < n; i++) if (s >> i & 1) res++;
return res;
}
int main () {
int _;
scanf("%d", &_);
while(_--) {
scanf("%d", &n);
sub[0] = sum[0] = 1;
for (int i = 0; i < n; i++) {
scanf("%d%d", l + i, r + i);
dp[i][0] = 1;
}
int tot = (1 << n);
for (int s = 1; s < tot; s++) {
sum[s] = sub[s] = 0;
int cnt = cal(s);
for (int i = 0; i < n; i++) {
dp[i][s] = 0;
if ((s >> i & 1) && l[i] <= cnt && cnt <= r[i]) {
dp[i][s] = sub[s ^ (1 << i)];
sum[s] = (sum[s] + dp[i][s]) % mod;
}
}
int j = 0;
for (j = 0; j < n; j++) if (s >> j & 1) break;
for (int left = s; left; left = (left - 1) & s) {
if (!(left >> j & 1)) continue;
sub[s] = (sub[s] + (sum[left] * sub[s ^ left]) % mod) % mod;
}
}
printf("%I64d\n", sum[tot - 1]);
}
return 0;
}

更新日志

  • 14564193 2015-08-19 00:21:01 Accepted 5103 327MS 3680K 1526 B G++ SIO__Five