qko-gym

[toc]

Day1

hdu6643

因为例题不仅有点分治还涉及到了树上依赖背包的算法,才发现自己并不太会树形背包的若干优化算法,故学习。

树形背包

模板题

给出一颗依赖树,询问总重量限定下可能获得的最大价值。

物品的数量和重量的限制均不超过100

有不同的做法,复杂度也不同。

向上合并

随意采取$O(nm^2)$的算法即可在树上合并。

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
const int manx = 1e2 + 10;

int n, W, v[maxn], w[maxn];
int dp[maxn][maxn];
star edge[maxn << 1];
int head[maxn], top = 0;

void add(int u, int v){
edge[top].to = v;
edge[top].next = head[u];
head[u] = top++;
}

//dp[i][j]表示i子树中重量为j下的最大价值
void dfs(int u, int par){
dp[u][w[u]] = v[u];

for(int i = head[u]; ~i; i = edge[i].next){
int to = edge[i].to; if(to == par) continue;
dfs(to, u);

for(int j = W; j >= w[u]; j--){
for(int k = j; k >= w[u]; k--){
if(dp[u][k] != -1 && dp[to][j - k] != -1)
dp[u][j] = max(dp[u][j], dp[u][k] + dp[to][j - k]);
}
}
}

}

int main(int argc, char *argv[]){
// Fastin;
clr(head, -1); clr(dp, -1);

scanf("%d %d", &n, &W);
for(int i = 1; i <= n; i++){
int x, y, z; scanf("%d %d %d", &x, &y, &z); if(z == -1) z = 0;
w[i] = x; v[i] = y;const int manx = 1e2 + 10;

int n, W, v[maxn], w[maxn];
int dp[maxn][maxn];
star edge[maxn << 1];
int head[maxn], top = 0;

void add(int u, int v){
// printf("%d %d\n",树形背包 u, v);
edge[top].to = v;
edge[top].next = head[u];
head[u] = top++;
}

//dp[i][j]表示i子树中重量为j下的最大价值
void dfs(int u, int par){
dp[u][0] = 0;
for(int i = head[u]; ~i; i = edge[i].next){
int to = edge[i].to; if(to == par) continue;

for(int i = 0; i <= W; i++) dp[to][i] = dp[u][i];
dfs(to, u);
for(int i = W; i >= w[to]; i--) if(dp[to][i - w[to]] != -1)
dp[u][i] = max(dp[u][i], dp[to][i - w[to]] + v[to]);
}
}

int main(int argc, char *argv[]){
// Fastin;
clr(head, -1); clr(dp, -1);

scanf("%d %d", &n, &W);
for(int i = 1; i <= n; i++){
int x, y, z; scanf("%d %d %d", &x, &y, &z); if(z == -1) z = 0;
w[i] = x; v[i] = y;
add(z, i);
}

dfs(0, -1);
int ans = 0; for(int i = 0; i <= W; i++) ans = max(ans, dp[0][i]);
printf("%d\n", ans);

return 0;
}

add(z, i);
}

dfs(0, -1);

int ans = 0; for(int i = 0; i <= W; i++) ans = max(ans, dp[0][i]);
printf("%d\n", ans);

return 0;
}

向下传递

在向下传递的更新背包过程时,dp数组的含义有了些许的变化。此时$dp[i][j]$表示选取i节点的子树且不允许选取i本身、总重量为j的最大价值。

将所有孩子的背包信息存在父节点的dp数组中,但不包含父亲自身的信息,每次传递、回收都只涉及到所有的儿子节点。因而在使用这种方法时,一定要使用一个 超级源点 来统一所有的信息!

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
const int manx = 1e2 + 10;

int n, W, v[maxn], w[maxn];
int dp[maxn][maxn];
star edge[maxn << 1];
int head[maxn], top = 0;

void add(int u, int v){
edge[top].to = v;
edge[top].next = head[u];
head[u] = top++;
}

//dp[i][j]表示i子树中重量为j下的最大价值
void dfs(int u, int par){fun
dp[u][0] = 0;
for(int i = head[u]; ~i; i = edge[i].next){
int to = edge[i].to; if(to == par) continue;

for(int i = 0; i <= W; i++) dp[to][i] = dp[u][i];
dfs(to, u);
for(int i = W; i >= w[to]; i--) if(dp[to][i - w[to]] != -1)
dp[u][i] = max(dp[u][i], dp[to][i - w[to]] + v[to]);
}
}

int main(int argc, char *argv[]){
// Fastin;
clr(head, -1); clr(dp, -1);

scanf("%d %d", &n, &W);
for(int i = 1; i <= n; i++){
int x, y, z; scanf("%d %d %d", &x, &y, &z); if(z == -1) z = 0;
w[i] = x; v[i] = y;
add(z, i);
}

dfs(0, -1);
int ans = 0; for(int i = 0; i <= W; i++) ans = max(ans, dp[0][i]);
printf("%d\n", ans);

return 0;
}

参考博客

树上依赖背包总结

dfs序优化

我们记录树的dfs序列,以及每个节点及其子树的大小。

有了这样的两个信息,我们就可以得到如下的转移方程

$dp[i][j] = max(dp[i + size[list[i]]][j], dp[i + 1][j - w[i]] + v[i])$

第一项表示完全不选这一棵子树,第二项则表示选这个子树并进行转移。

非常的精妙。

参考博客压缩

先序遍历优化树形背包

乘积压缩

当转移之间的关系不是加法而是乘法时,如果使用一般的方式空间利用密度较低,可以考虑使用一种压缩的方式达到$O(\sqrt W)$的状态空间。

具体来说,设置$dp[i]$表示乘积$\prod a_i$满足关系 $\frac {W}{\prod a_i}=i$ 的某价值。

从x到xy转移时即为从dp[W / x]到dp[W / x / y]转移。

AC下

在本题中,利用点分治限制树的深度,每次暴力遍历子树,复杂度$O(nlogn)$

在遍历子树时,记录当前根下每个子树的大小以及dfn序列。

有了上述两个信息,我们就可以更新依赖背包。

本题要计数的是连通块的个数,而不是平常的最大背包价值,因而在dp转移时有所不同。

$dp[i][j]$由两部分构成,一部分是dfn[i]节点本身子树构成的总重量为j的计数方案,另一部分递归地继承dfs树上i的右兄弟的若干信息。因而除了根节点的dp数组为其真实情况,其余节点的dp数组均有一些继承右兄弟而来的计数方案,仅在前一个dfn元素就是其父亲时将这些贡献统一地传递给父亲。

接下来用到乘积压缩即可,写的比较丑,将一一映射的关系进行保存,每次仅仅对这$\sqrt W$个可能的状态进行转移即可。

基本的思路就是这些,把自己坑了一下午的点是最开始写的时候认为getroot后sove(root)时,当前连通块内每个节点的子树大小就是getroot处理出来的大小。这显然是错误的,一旦getroot换根后,子树大小显然也会发生改变,应该重新计数!

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
const int maxn = 2e3 + 10;
const int maxe = 1e6 + 10;
const int K = 2e3 + 10;
const int M = 1e9 + 7;

int n, W;
int head[maxn], top = 0;
int w[maxn];
star edge[maxe << 1];
void add(int u, int v){
edge[top].to = v;
edge[top].next = head[u];
head[u] = top++;
}

int mx[maxn], root, vis[maxn], S, sze[maxn];
void getroot(int now, int par){
sze[now] = 1; mx[now] = 0;
for(int i = head[now]; ~i; i = edge[i].next){
int to = edge[i].to; if(vis[to] || to == par) continue;
getroot(to, now);
sze[now] += sze[to];
mx[now] = max(mx[now], sze[to]);
}
mx[now] = max(mx[now], S - mx[now]);
if(mx[now] < mx[root]) root = now;
}

int dfn[maxn], cnt = 0;
void dfs(int now, int par){
dfn[cnt++] = now; sze[now] = 1;
for(int i = haed[now]; ~i; i = edge[i].next){
int to = edge[i].to; if(vis[to] || par == to) continue;
dfs(to, now);
sze[now] += sze[to];
}
}
ll ans = 0;
ll dp[maxn][K];
vector<int> vec;
int mp[K * K];

void fun(int now){
cnt = 0; dfs(now, -1);

for(int i = 0; i <= cnt; i++) for(int j = 0; j < vec.size(); j++) dp[i][j] = 0;
dp[cnt][0] = 1;

for(int i = cnt - 1; i >= 0; i--){
int u = dfn[i];
for(int j = 0; j < vec.size(); j++){
if(vec[j] / w[u]){
int pos = mp[vec[j] / w[u]];

dp[i][pos] += dp[i + 1][j];
dp[i][pos] %= M;
}
dp[i][j] += dp[i + sze[u]][j];
dp[i][j] %= M;
}
}
for(int i = 0; i < (itn)vec.size(); i++) ans = (ans + dp[0][i]) % M;
ans = (ans + M - 1) % M;
}

void sove(int now){
vis[now] = 1;
fun(now);

for(int i = head[now]; ~i; i = edge[i].next){
int to = edge[i].to; if(vis[to]) continue;

S = sze[to]; root = 0;
getroot(to, now);
sove(root);
}
}

int main(){
// Fastin;
TTT{
ans = 0;
clr(head, -1); top = 0;
scanf("%d %d", &n, &W);
for(int i = 1; i <= n; i++) scnaf("%d", w + i);
for(int i = 0; i < n - 1; i++){
int u, v; scanf("%d %d", &u, &v);
add(u, v); add(v, u);
}
vec.clear(); clr(mp, 0);
for(int i = 1; i <= W; i++){
int res = W / i;
if(vec.empty() || *vec.rbegin() != res) vec.push_back(res);
}
for(int i = 0; i < vec.size(); i++) mp[vec[i]] = i;


root = 0;
S = mx[0] = n;
clr(vis, 0); clr(dp, -1);
getroot(1, 0); sove(root);

printf("%lld\n", ans);
}

return 0;
}