×

计蒜客

  1. 题库
  2. 卡尔的连招
  3. 问答
  • 25%
  • 65536K

题目描述

玩dota的时候,使用祈求者这个英雄非常有趣。设该英雄有N个技能,每个技能只能放一次。每个技能有基础伤害 $A_i$ (0 <= i <= N - 1)。每个技能有 $M_i$ (0 <= i <= N - 1)条连招。每条连招包含两个整数 $B_j$,$C_j$ (1 <= j <= $M_i$)以及 $C_j$ 个技能id。连招的意义是,当放i技能之前,$C_j$个技能都已经放过了,则i技能的伤害会变成$B_j$。因此,技能的施放顺序会影响技能的伤害值。

我们的目的是找到最优的技能施放顺序使得造成的伤害和最大,请输出最大的和。

输入格式

一个整数T,表示一共有T组测试用例。

接下来T组测试用例,每组测试用例包含如下部分:

第一行为一个整数N,表示共有N个技能,技能编号为 0 到 N - 1。接下来N组数据描述每个技能的信息。

每组数据的第一行为两个整数 $A_i$, $M_i$。表示第i个技能的基础伤害 $A_i$,和第i个技能有 $M_i$ 条连招。接下来 $M_i$ 行给出连招的信息。每行先给出两个整数 $B_j$, $C_j$,再给出 $C_j$ 个整数 $ID_k$ (1 <= k <= $C_j$)。表示当 $C_j$ 个技能在i之前都放过,i的技能伤害变为$B_j$。

数据范围如下:

1 <= T <= 10

1 <= N <= 15

1 <= $A_i$ < $B_j$ <= 100000

1 <= $M_i$ <= 1000

1 <= $C_j$ <= N - 1

0 <= $ID_k$ <= N - 1 并且 $ID_k$ 不等于 i。

输出格式

一个整数,表示最大伤害和。

样例输入

1
2
50 1
60 1 1
70 1
90 1 0

样例输出

140

题目来源

北方大学 ACM 多校训练赛 第十四场

想挑战这道题吗

  • main.c