我是靠谱客的博主 感动西牛,这篇文章主要介绍2020 ICPC南京 M.Monster Hunter(树形背包),现在分享给大家,希望可以做个参考。

题目大意

  给你一棵树,你可以去掉i个点( i ∈ [ 0 , n ] iin[0,n] i[0,n]),然后计算剩余结点的贡献,每个结点的贡献为它本身的价值加上它所有儿子的价值。当然你需要合理安排删去的i个结点使贡献最小化。输出每个i对应的贡献值。

解体思路

  树形dp,由于结点的贡献与周边的结点有关,所以还需要再开一维状态
状态设计
d p [ 0 ] [ i ] [ j ] dp[0][i][j] dp[0][i][j] 表示删掉结点i,并且子树中留下j个结点的价值。
d p [ 1 ] [ i ] [ j ] dp[1][i][j] dp[1][i][j] 表示留下结点i,并且子树中留下j-1个结点的价值。
状态转移
d p [ 0 ] [ i ] [ j + k ] = m i n ( f [ 0 ] [ i ] [ j + k ] , f [ 0 ] [ i ] [ j ] + m i n ( f [ 0 ] [ s o n ] [ k ] , f [ 1 ] [ s o n ] [ k ] ) ) dp[0][i][j+k] = min(f[0][i][j+k],f[0][i][j]+min(f[0][son][k],f[1][son][k])) dp[0][i][j+k]=min(f[0][i][j+k],f[0][i][j]+min(f[0][son][k],f[1][son][k]))
d p [ 1 ] [ i ] [ j + k ] = m i n ( f [ 1 ] [ i ] [ j + k ] , f [ 1 ] [ i ] [ j ] + m i n ( f [ 0 ] [ s o n ] [ k ] , f [ 1 ] [ s o n ] [ k ] + a [ s o n ] ) ) dp[1][i][j+k] = min(f[1][i][j+k],f[1][i][j]+min(f[0][son][k],f[1][son][k] + a[son])) dp[1][i][j+k]=min(f[1][i][j+k],f[1][i][j]+min(f[0][son][k],f[1][son][k]+a[son]))
其中a数组存储的是结点的价值
边界条件
f [ 0 ] [ i ] [ 0 ] = 0 f[0][i][0] = 0 f[0][i][0]=0
f [ 1 ] [ i ] [ 1 ] = a [ i ] f[1][i][1]=a[i] f[1][i][1]=a[i]

代码实现

注意dp时边界的确定,否则复杂度不是O(n)的
循环中第一维倒序枚举的原因是运用了滚动数组

复制代码
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
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e3 +5; const int MAXM = 4e3 +5; #define ll long long const ll inf = 1e18; int head[MAXN], nxt[MAXM], to[MAXM], sze[MAXN], a[MAXN], n, tot; inline void AddEdge(int u, int v) { nxt[++tot] = head[u], to[head[u] = tot] = v; } ll f[2][MAXN][MAXN]; void dfs(int u) { f[0][u][0] = 0; f[1][u][1] = a[u]; for(int e = head[u]; e; e=nxt[e]) dfs(to[e]); sze[u] = 1; for (int e = head[u]; e; e = nxt[e]) { for (int j = sze[u]; j >= 0; j--) { for (int k = sze[to[e]]; k >= 0; k--) { f[0][u][j + k] = min(f[0][u][j + k], f[0][u][j] + min(f[0][to[e]][k], f[1][to[e]][k])); f[1][u][j + k] = min(f[1][u][j + k], f[1][u][j] + min(f[0][to[e]][k], f[1][to[e]][k] + a[to[e]])); } } sze[u] += sze[to[e]]; } } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) head[i] = 0; tot = 0; for (int i = 2; i <= n; i++) { int u; scanf("%d", &u); AddEdge(u, i); } for (int i = 1; i <= n; i++) scanf("%d", a + i); for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) f[0][i][j] = f[1][i][j] = inf; dfs(1); for (int i = 0; i <= n; i++) printf("%lld%c", min(f[0][1][n - i], f[1][1][n - i]), " n"[i == n]); } return 0; }

最后

以上就是感动西牛最近收集整理的关于2020 ICPC南京 M.Monster Hunter(树形背包)的全部内容,更多相关2020内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(77)

评论列表共有 0 条评论

立即
投稿
返回
顶部