#P17789. Jellyfish and Inscryption
Jellyfish and Inscryption
题目描述
水母喜欢玩一个叫做“Inscryption”的游戏,这个游戏在一个有向无环图上进行,图中有 个顶点和 条边。所有的边 都满足 。
你需要沿着有向边从顶点 移动到顶点 ,然后与最终 Boss 战斗。
在这个过程中,你会收集卡牌和道具。
每张卡牌有两个属性:生命值(HP)和伤害(damage)。如果一张卡牌的生命值为 ,伤害为 ,那么这张卡牌的能量为 。
每个道具只有一个属性:能量值(power)。
除了顶点 和顶点 ,有一些顶点会触发特殊事件。特殊事件包括:
- 你会获得一张生命值为 ,伤害为 的卡牌。
- 如果你至少有一张卡牌,选择你的一张卡牌并使其生命值增加 。
- 如果你至少有一张卡牌,选择你的一张卡牌并使其伤害增加 。
- 你会获得一个能量值为 的道具。
当你到达顶点 时,你可以选择至多一张你的卡牌,并将其伤害乘以 。
最终 Boss 非常强大,因此你希望最大化你所有卡牌和道具的能量之和。请你求出如果你最优地进行游戏,所有卡牌和道具的能量之和的最大值。
输入格式
第一行包含两个整数 和 (,)——顶点数和边数。
接下来的 行中,第 行()描述了在顶点 触发的特殊事件:
- 0 —— 没有特殊事件。
- 1 a b()——你会获得一张生命值为 ,伤害为 的卡牌。
- 2 x()——如果你至少有一张卡牌,选择你的一张卡牌并使其生命值增加 。
- 3 y()——如果你至少有一张卡牌,选择你的一张卡牌并使其伤害增加 。
- 4 w()——你会获得一个能量值为 的道具。
接下来的 行,每行包含两个整数 和 (),表示一条从顶点 到顶点 的有向边。
保证每条边 最多出现一次。
保证顶点 和顶点 没有特殊事件。
保证对于所有 ,存在一条从顶点 到顶点 的路径经过顶点 。
输出格式
输出一个整数,表示你所有卡牌和道具的能量之和的最大值。
输入输出样例 #1
输入 #1
6 8
0
1 2 10
1 6 6
2 8
3 10
0
1 2
1 3
2 4
2 5
3 4
3 5
4 6
5 6
输出 #1
100000000000
输入输出样例 #2
输入 #2
4 3
0
4 1000000
4 1000000
0
1 2
2 3
3 4
输出 #2
2000000
输入输出样例 #3
输入 #3
16 15
0
1 1 10
1 10 1
2 4
3 4
1 20 20
2 30
3 20
1 1 100
2 9
1 1 200
2 9
3 10
1 190 100
2 10
0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
输出 #3
20000000005600
输入输出样例 #4
输入 #4
9 9
0
1 1 200
3 200
3 200
3 200
3 200
1 200 200
3 200
0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
1 9
输出 #4
80000000001000
输入输出样例 #5
输入 #5
9 8
0
1 20 200
3 200
3 200
2 5
1 100 200
3 200
3 200
0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
输出 #5
60000000015000
输入输出样例 #6
输入 #6
16 34
0
0
0
2 6
3 1
4 27
4 40
3 9
0
2 6
1 8 1
0
2 2
1 10 7
2 9
0
2 4
3 10
2 11
2 7
13 15
3 15
2 3
6 14
4 12
10 12
9 10
7 8
4 13
11 12
4 6
11 16
14 15
2 5
5 15
9 13
8 14
1 3
2 15
12 16
7 10
4 5
1 2
4 11
4 9
4 16
3 6
6 8
7 11
15 16
输出 #6
133000000040
说明/提示
在第一个样例中,我们可以按如下顺序进行游戏:
- 从顶点 移动到顶点 ,获得一张生命值为 ,伤害为 的卡牌。
- 从顶点 移动到顶点 ,选择在顶点 获得的卡牌,并使其生命值增加 。
- 从顶点 移动到顶点 ,选择在顶点 获得的卡牌,并将其伤害乘以 。
最终,我们会有一张生命值为 ,伤害为 的卡牌,其能量为 。因为我们只有在顶点 获得的这张卡牌,所以所有卡牌和道具的能量之和为 。
由 ChatGPT 4.1 翻译