qko-gym



 2021.04.02 21:10  2023.09.01 18:14  ACM  树形背包  乘积压缩  点分治 󰈭 2247字

Day1

hdu6643

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

树形背包

模板题

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

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

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

向上合并

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

 1const int manx = 1e2 + 10;
 2
 3int n, W, v[maxn], w[maxn];
 4int dp[maxn][maxn];
 5star edge[maxn << 1];
 6int head[maxn], top = 0;
 7
 8void add(int u, int v){
 9    edge[top].to = v;
10    edge[top].next = head[u];
11    head[u] = top++;
12}
13
14//dp[i][j]表示i子树中重量为j下的最大价值
15void dfs(int u, int par){
16    dp[u][w[u]] = v[u];
17    
18    for(int i = head[u]; ~i; i = edge[i].next){
19        int to = edge[i].to; if(to == par) continue;
20        dfs(to, u);
21
22        for(int j = W; j >= w[u]; j--){
23            for(int k = j; k >= w[u]; k--){
24                if(dp[u][k] != -1 && dp[to][j - k] != -1)
25                    dp[u][j] = max(dp[u][j], dp[u][k] + dp[to][j - k]);
26            }
27        }
28    }
29
30}
31
32int main(int argc, char *argv[]){
33    // Fastin; 
34    clr(head, -1); clr(dp, -1);
35    
36    scanf("%d %d", &n, &W);
37    for(int i = 1; i <= n; i++){
38        int x, y, z; scanf("%d %d %d", &x, &y, &z); if(z == -1) z = 0;
39        w[i] = x; v[i] = y;const int manx = 1e2 + 10;
40
41int n, W, v[maxn], w[maxn];
42int dp[maxn][maxn];
43star edge[maxn << 1];
44int head[maxn], top = 0;
45
46void add(int u, int v){
47    // printf("%d %d\n",树形背包 u, v);
48    edge[top].to = v;
49    edge[top].next = head[u];
50    head[u] = top++;
51}
52
53//dp[i][j]表示i子树中重量为j下的最大价值
54void dfs(int u, int par){
55    dp[u][0] = 0;
56    for(int i = head[u]; ~i; i = edge[i].next){
57        int to = edge[i].to; if(to == par) continue;
58
59        for(int i = 0; i <= W; i++) dp[to][i] = dp[u][i];
60        dfs(to, u);
61        for(int i = W; i >= w[to]; i--) if(dp[to][i - w[to]] != -1)
62            dp[u][i] = max(dp[u][i], dp[to][i - w[to]] + v[to]);
63    } 
64}
65
66int main(int argc, char *argv[]){
67    // Fastin; 
68    clr(head, -1); clr(dp, -1);
69    
70    scanf("%d %d", &n, &W);
71    for(int i = 1; i <= n; i++){
72        int x, y, z; scanf("%d %d %d", &x, &y, &z); if(z == -1) z = 0;
73        w[i] = x; v[i] = y;
74        add(z, i);
75    }
76    
77    dfs(0, -1);
78    int ans = 0; for(int i = 0; i <= W; i++) ans = max(ans, dp[0][i]);
79    printf("%d\n", ans);
80
81    return 0;
82}
83
84        add(z, i);
85    }
86    
87    dfs(0, -1);
88
89    int ans = 0; for(int i = 0; i <= W; i++) ans = max(ans, dp[0][i]);
90    printf("%d\n", ans);
91
92    return 0;
93}

向下传递

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

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

 1const int manx = 1e2 + 10;
 2
 3int n, W, v[maxn], w[maxn];
 4int dp[maxn][maxn];
 5star edge[maxn << 1];
 6int head[maxn], top = 0;
 7
 8void add(int u, int v){
 9    edge[top].to = v;
10    edge[top].next = head[u];
11    head[u] = top++;
12}
13
14//dp[i][j]表示i子树中重量为j下的最大价值
15void dfs(int u, int par){fun
16    dp[u][0] = 0;
17    for(int i = head[u]; ~i; i = edge[i].next){
18        int to = edge[i].to; if(to == par) continue;
19
20        for(int i = 0; i <= W; i++) dp[to][i] = dp[u][i];
21        dfs(to, u);
22        for(int i = W; i >= w[to]; i--) if(dp[to][i - w[to]] != -1)
23            dp[u][i] = max(dp[u][i], dp[to][i - w[to]] + v[to]);
24    } 
25}
26
27int main(int argc, char *argv[]){
28    // Fastin; 
29    clr(head, -1); clr(dp, -1);
30    
31    scanf("%d %d", &n, &W);
32    for(int i = 1; i <= n; i++){
33        int x, y, z; scanf("%d %d %d", &x, &y, &z); if(z == -1) z = 0;
34        w[i] = x; v[i] = y;
35        add(z, i);
36    }
37    
38    dfs(0, -1);
39    int ans = 0; for(int i = 0; i <= W; i++) ans = max(ans, dp[0][i]);
40    printf("%d\n", ans);
41
42    return 0;
43}

参考博客

树上依赖背包总结

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换根后，子树大小显然也会发生改变，应该重新计数！

  1const int maxn = 2e3 + 10;
  2const int maxe = 1e6 + 10;
  3const int K =  2e3 + 10;
  4const int M = 1e9 + 7;
  5
  6int n, W;
  7int head[maxn], top = 0;
  8int w[maxn];
  9star edge[maxe << 1];
 10void add(int u, int v){
 11    edge[top].to = v;
 12    edge[top].next = head[u];
 13    head[u] = top++;
 14}
 15
 16int mx[maxn], root, vis[maxn], S, sze[maxn];
 17void getroot(int now, int par){
 18    sze[now] = 1; mx[now] = 0;
 19    for(int i = head[now]; ~i; i = edge[i].next){
 20        int to = edge[i].to; if(vis[to] || to == par) continue;
 21        getroot(to, now);
 22        sze[now] += sze[to];
 23        mx[now] = max(mx[now], sze[to]);
 24    }
 25    mx[now] = max(mx[now], S - mx[now]);
 26    if(mx[now] < mx[root]) root = now;
 27}
 28
 29int dfn[maxn], cnt = 0;
 30void dfs(int now, int par){
 31    dfn[cnt++] = now; sze[now] = 1;
 32    for(int i = haed[now]; ~i; i = edge[i].next){
 33        int to = edge[i].to; if(vis[to] || par == to) continue;
 34        dfs(to, now);
 35        sze[now] += sze[to];
 36    }
 37}
 38ll ans = 0;
 39ll dp[maxn][K];
 40vector<int> vec;
 41int mp[K * K];
 42
 43void fun(int now){
 44    cnt = 0; dfs(now, -1);
 45
 46    for(int i = 0; i <= cnt; i++) for(int j = 0; j < vec.size(); j++) dp[i][j] = 0;
 47    dp[cnt][0] = 1;
 48
 49    for(int i = cnt - 1; i >= 0; i--){
 50        int u = dfn[i];
 51        for(int j = 0; j < vec.size(); j++){
 52            if(vec[j] / w[u]){
 53                int pos = mp[vec[j] / w[u]];
 54                
 55                dp[i][pos] += dp[i + 1][j];
 56                dp[i][pos] %= M;
 57            }
 58            dp[i][j] += dp[i + sze[u]][j];
 59            dp[i][j] %= M;
 60        }
 61    }
 62    for(int i = 0; i < (itn)vec.size(); i++) ans = (ans + dp[0][i]) % M;
 63    ans = (ans + M - 1) % M;
 64}
 65
 66void sove(int now){
 67    vis[now] = 1; 
 68    fun(now);
 69    
 70    for(int i = head[now]; ~i; i = edge[i].next){
 71        int to = edge[i].to; if(vis[to]) continue;
 72
 73        S = sze[to]; root = 0;
 74        getroot(to, now);
 75        sove(root);
 76    }
 77}
 78
 79int main(){
 80    // Fastin; 
 81    TTT{
 82        ans = 0;
 83        clr(head, -1); top = 0;
 84        scanf("%d %d", &n, &W);
 85        for(int i = 1; i <= n; i++) scnaf("%d", w + i);
 86        for(int i = 0; i < n - 1; i++){
 87            int u, v; scanf("%d %d", &u, &v);
 88            add(u, v); add(v, u);
 89        }
 90        vec.clear(); clr(mp, 0);
 91        for(int i = 1; i <= W; i++){
 92            int res = W / i; 
 93            if(vec.empty() || *vec.rbegin() != res) vec.push_back(res);
 94        }
 95        for(int i = 0; i < vec.size(); i++) mp[vec[i]] = i;
 96
 97
 98        root = 0;
 99        S = mx[0] = n;
100        clr(vis, 0); clr(dp, -1);
101        getroot(1, 0); sove(root);
102
103        printf("%lld\n", ans);
104    }
105
106    return 0;
107}