题目链接
题目描述
There is a rooted tree with
n
n
n vertices and the root vertex is
1
1
1. In each vertex, there is a monster. The hit points of the monster in the
i
i
i-th vertex is
h
p
i
hp_i
hpi .
Kotori would like to kill all the monsters. The monster in the i i i-th vertex could be killed if the monster in the direct parent of the i i i-th vertex has been killed. The power needed to kill the i i i-th monster is the sum of h p i hp_i hpi and the hit points of all other living monsters who lives in a vertex j j j whose direct parent is i i i. Formally, the power equals to
h
p
i
+
∑
the monster in vertex
j
is alive
and
i
is the direct parent of
j
h
p
j
hp_i + sumlimits_{begin{array}{c}text{the monster in vertex } j text{ is alive} \ text{and } i text{ is the direct parent of } j end{array}} hp_j
hpi+the monster in vertex j is aliveand i is the direct parent of j∑hpj
In addition, Kotori can use some magic spells. If she uses one magic spell, she can kill any monster using 0 0 0 power without any restriction. That is, she can choose a monster even if the monster in the direct parent is alive.
For each
m
=
0
,
1
,
2
,
⋯
,
n
m=0,1,2,cdots,n
m=0,1,2,⋯,n , Kotori would like to know, respectively, the minimum total power needed to kill all the monsters if she can use mm magic spells.
输入描述:
There are multiple test cases. The first line of input contains an integer
T
T
T indicating the number of test cases. For each test case:
The first line contains an integer n n n ( 2 ≤ n ≤ 2 × 1 0 3 ) (2 le n le 2 times 10^3 ) (2≤n≤2×103), indicating the number of vertices.
The second line contains ( n − 1 ) (n-1) (n−1) integers p 2 , p 3 , ⋯ , p n p_2,p_3,cdots,p_n p2,p3,⋯,pn ( 1 ≤ p i < i ) (1 le p_i < i) (1≤pi<i) , where p i p_i pi means the direct parent of vertex i i i.
The third line contains nn integers h p 1 , h p 2 , ⋯ , h p n hp_1,hp_2,cdots,hp_n hp1,hp2,⋯,hpn ( 1 ≤ h p i ≤ 1 0 9 ) (1 le hp_i le 10^9 ) (1≤hpi≤109) indicating the hit points of each monster.
It’s guaranteed that the sum of nn of all test cases will not exceed
2
×
1
0
3
2 times 10^3
2×103 .
输出描述:
For each test case output one line containing
(
n
+
1
)
(n+1)
(n+1) integers
a
0
,
a
1
,
⋯
,
a
n
a_0, a_1, cdots, a_n
a0,a1,⋯,an separated by a space, where
a
m
a_m
am indicates the minimum total power needed to kill all the monsters if Kotori can use
m
m
m magic spells.
Please, DO NOT output extra spaces at the end of each line, otherwise your answer may be considered incorrect!
示例1
输入
1
2
3
4
5
6
7
8
9
10
113 5 1 2 3 4 1 2 3 4 5 9 1 2 3 4 3 4 6 6 8 4 9 4 4 5 2 4 1 12 1 2 2 4 5 3 4 3 8 10 11 9 1 3 5 10 10 7 3 7 9 4 9
输出
1
2
3
429 16 9 4 1 0 74 47 35 25 15 11 7 3 1 0 145 115 93 73 55 42 32 22 14 8 4 1 0
E因为写分类讨论卡了近两个半小时，M题思路秒出，结果因为背包生疏到比赛结束都没有调过样例（虽然调出来也是T ）最终四题铜QAQ。。
首先，对于特定的咒语使用方案，power的总和也是确定的，因此考虑dp咒语使用方案。
设状态
f
[
x
]
[
i
]
[
0
/
1
]
f[x][i][0/1]
f[x][i][0/1] 表示以
x
x
x 为根的子树使用
i
i
i 个咒语且节点
i
i
i 是/否被使用咒语时power和的最小值。
则状态转移方程为：
{
f
[
x
]
[
i
]
[
1
]
=
min
(
∑
y
0
,
y
1
∈
s
o
n
x
∑
i
0
+
∑
i
1
=
i
f
[
y
0
]
[
i
0
]
[
0
]
+
f
[
y
1
]
[
i
1
]
[
1
]
+
h
p
[
y
1
]
)
+
h
p
[
x
]
f
[
x
]
[
i
]
[
0
]
=
min
(
∑
y
0
,
y
1
∈
s
o
n
x
∑
i
0
+
∑
i
1
=
i
−
1
f
[
y
0
]
[
i
0
]
[
0
]
+
f
[
y
1
]
[
i
1
]
[
1
]
)
left{begin{matrix} f[x][i][1] =&min(sumlimits_{y_0,y_1 in son_x sum i_0+sum i_1=i}f[y_0][i_0][0]+f[y_1][i_1][1]+hp[y_1]) +hp[x]\ f[x][i][0] =&min(sumlimits_{y_0,y_1 in son_x sum i_0+sum i_1=i-1}f[y_0][i_0][0]+f[y_1][i_1][1]) end{matrix}right.
⎩⎪⎨⎪⎧f[x][i][1]=f[x][i][0]=min(y0,y1∈sonx ∑i0+∑i1=i∑f[y0][i0][0]+f[y1][i1][1]+hp[y1])+hp[x]min(y0,y1∈sonx ∑i0+∑i1=i−1∑f[y0][i0][0]+f[y1][i1][1])
注意同样的转移方程不同的写法转移次数是不同的，具体区别看下面两份代码。
TLE代码
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#include<bits/stdc++.h> using namespace std; inline int qr() { int f = 0, fu = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-')fu = -1; c = getchar(); } while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + c - 48; c = getchar(); } return f * fu; } const int N = 2e3 + 10; const long long INF = 1e18; int head[N], ver[N], Next[N], tot; int T, n, siz[N], hp[N]; long long f[N][N][2], g[N][2]; inline void add(int x, int y) { ver[++tot] = y; Next[tot] = head[x]; head[x] = tot; } inline void init() { tot = 0; memset(head, 0, sizeof(int) * (n + 1)); for (int i = 1; i <= n; ++i) for (int j = 0; j <= n; ++j) f[i][j][0] = f[i][j][1] = 0; } void dp(int x) { siz[x] = 1; if (!head[x]) { f[x][0][0] = INF, f[x][0][1] = hp[x]; f[x][1][0] = 0, f[x][1][1] = INF; return; } for (int i = head[x]; i; i = Next[i]) { int y = ver[i]; dp(y), siz[x] += siz[y]; for (int j = 0; j <= siz[x]; ++j)g[j][1] = g[j][0] = INF; for (int j = 0; j <= siz[x]; ++j) for (int k = 0; k <= min(j, siz[y]); ++k) { if (j < siz[x])g[j][1] = min(g[j][1], f[x][j - k][1] + min(f[y][k][0], f[y][k][1] + hp[y])); if (j > k)g[j][0] = min(g[j][0], f[x][j - k][0] + min(f[y][k][0], f[y][k][1])); } for (int j = 0; j <= siz[x]; ++j)f[x][j][1] = g[j][1]; for (int j = 0; j <= siz[x]; ++j)f[x][j][0] = g[j][0]; } for (int i = 0; i <= siz[x] - 1; ++i)f[x][i][1] += hp[x]; } int main() { T = qr(); while (T--) { n = qr(), init(); for (int i = 2; i <= n; ++i)add(qr(), i); for (int i = 1; i <= n; ++i)hp[i] = qr(); dp(1); for (int i = 0; i <= n; ++i) printf("%lld%c", min(f[1][i][0], f[1][i][1]), i == n ? 'n' : ' '); } return 0; }
AC代码
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#include<bits/stdc++.h> using namespace std; inline int qr() { int f = 0, fu = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-')fu = -1; c = getchar(); } while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + c - 48; c = getchar(); } return f * fu; } const int N = 2e3 + 10; const long long INF = 1e18; int head[N], ver[N], Next[N], tot; int T, n, siz[N], hp[N]; long long f[N][N][2], g[N][2]; inline void add(int x, int y) { ver[++tot] = y; Next[tot] = head[x]; head[x] = tot; } inline void init() { tot = 0; memset(head, 0, sizeof(int) * (n + 1)); for (int i = 1; i <= n; ++i) for (int j = 0; j <= n; ++j) f[i][j][0] = f[i][j][1] = 0; } void dp(int x) { siz[x] = 1; if (!head[x]) { f[x][0][0] = INF, f[x][0][1] = hp[x]; f[x][1][0] = 0, f[x][1][1] = INF; return; } for (int i = head[x]; i; i = Next[i]) { int y = ver[i]; dp(y); for (int j = 0; j <= siz[x] + siz[y]; ++j) g[j][1] = g[j][0] = INF; for (int j = 0; j <= siz[x]; ++j) for (int k = 0; k <= siz[y]; ++k) { if (j + k < siz[x] + siz[y]) g[j + k][1] = min(g[j + k][1], f[x][j][1] + min(f[y][k][0], f[y][k][1] + hp[y])); if (j > 0)g[j + k][0] = min(g[j + k][0], f[x][j][0] + min(f[y][k][0], f[y][k][1])); } siz[x] += siz[y]; for (int j = 0; j <= siz[x]; ++j)f[x][j][1] = g[j][1]; for (int j = 0; j <= siz[x]; ++j)f[x][j][0] = g[j][0]; } for (int i = 0; i <= siz[x] - 1; ++i)f[x][i][1] += hp[x]; } int main() { T = qr(); while (T--) { n = qr(), init(); for (int i = 2; i <= n; ++i)add(qr(), i); for (int i = 1; i <= n; ++i)hp[i] = qr(); dp(1); for (int i = 0; i <= n; ++i) printf("%lld%c", min(f[1][i][0], f[1][i][1]), i == n ? 'n' : ' '); } return 0; }
最后
以上就是辛勤鸭子最近收集整理的关于2020ICPC南京 M.Monster Hunter的全部内容，更多相关2020ICPC南京内容请搜索靠谱客的其他文章。
发表评论 取消回复