题目大意
给你一棵树,你可以去掉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内容请搜索靠谱客的其他文章。
发表评论 取消回复