6174: 装饰珠
[Creator : ]
Description
在怪物猎人这一款游戏中,玩家可以通过给装备镶嵌不同的装饰珠来获取 相应的技能,以提升自己的战斗能力。
已知猎人身上一共有 $6$ 件装备,每件装备可能有若干个装饰孔,每个装饰孔有各自的等级,可以镶嵌一颗小于等于自身等级的装饰珠 (也可以选择不镶嵌)。
装饰珠有 $M$ 种,编号 $1$ 至 $M$,分别对应 $M$ 种技能,第 $i$ 种装饰珠的等级为 $L_i$,只能镶嵌在等级大于等于 $L_i$ 的装饰孔中。
对第 $i$ 种技能来说,当装备相应技能的装饰珠数量达到 $K_i$ 个时,会产生 $W_i(K_i)$ 的价值。镶嵌同类技能的数量越多,产生的价值越大,即 $W_i(K_i − 1) < W_i(K_i)$。但每个技能都有上限 $P_i\ (1 \leq P_i \leq 7)$,当装备的珠子数量超过 $P_i$ 时,只会产生 $W_i(P_i)$ 的价值。
对于给定的装备和装饰珠数据,求解如何镶嵌装饰珠,使得 $6$ 件装备能得到的总价值达到最大。
已知猎人身上一共有 $6$ 件装备,每件装备可能有若干个装饰孔,每个装饰孔有各自的等级,可以镶嵌一颗小于等于自身等级的装饰珠 (也可以选择不镶嵌)。
装饰珠有 $M$ 种,编号 $1$ 至 $M$,分别对应 $M$ 种技能,第 $i$ 种装饰珠的等级为 $L_i$,只能镶嵌在等级大于等于 $L_i$ 的装饰孔中。
对第 $i$ 种技能来说,当装备相应技能的装饰珠数量达到 $K_i$ 个时,会产生 $W_i(K_i)$ 的价值。镶嵌同类技能的数量越多,产生的价值越大,即 $W_i(K_i − 1) < W_i(K_i)$。但每个技能都有上限 $P_i\ (1 \leq P_i \leq 7)$,当装备的珠子数量超过 $P_i$ 时,只会产生 $W_i(P_i)$ 的价值。
对于给定的装备和装饰珠数据,求解如何镶嵌装饰珠,使得 $6$ 件装备能得到的总价值达到最大。
Input
输入的第 $1$ 至 $6$ 行,包含 $6$ 件装备的描述。其中第 $i$ 行的第一个整数 $N_i$ 表示第 $i$ 件装备的装饰孔数量。后面紧接着 $N_i$ 个整数,分别表示该装备上每个装饰孔的等级 $L\ (1 \leq L \leq 4)$。
第 $7$ 行包含一个正整数 $M$,表示装饰珠 (技能) 种类数量。
第 $8$ 至 $M + 7$ 行,每行描述一种装饰珠 (技能) 的情况。每行的前两个整数 $L_j\ (1 \leq L_j \leq 4),\ P_j\ (1 \leq P_i \leq 7)$ 分别表示第 $j$ 种装饰珠的等级和上限。接下来 $P_j$ 个整数,其中第 $k$ 个数表示该装备中装饰珠数量为 $k$ 时的价值 $W_j(k)$。
其中,$1 \leq N_i \leq 50,\ 1 \leq M \leq 10^4,\ 1 \leq W_j(k) \leq 10^4$。
第 $7$ 行包含一个正整数 $M$,表示装饰珠 (技能) 种类数量。
第 $8$ 至 $M + 7$ 行,每行描述一种装饰珠 (技能) 的情况。每行的前两个整数 $L_j\ (1 \leq L_j \leq 4),\ P_j\ (1 \leq P_i \leq 7)$ 分别表示第 $j$ 种装饰珠的等级和上限。接下来 $P_j$ 个整数,其中第 $k$ 个数表示该装备中装饰珠数量为 $k$ 时的价值 $W_j(k)$。
其中,$1 \leq N_i \leq 50,\ 1 \leq M \leq 10^4,\ 1 \leq W_j(k) \leq 10^4$。
Output
输出一行包含一个整数,表示能够得到的最大价值。
Sample 1 Input
1 1
2 1 2
1 1
2 2 2
1 1
1 3
3
1 5 1 2 3 5 8
2 4 2 4 8 15
3 2 5 10
Sample 1 Output
20
按照如下方式镶嵌珠子得到最大价值 $18$,括号内表示镶嵌的装饰珠的种类编号:
1: (1)
2: (1) (2)
3: (1)
4: (2) (2)
5: (1)
6: (2)
$4$ 颗技能 $1$ 装饰珠,$4$ 颗技能 $2$ 装饰珠。
$W_1(4) + W_2(4) = 5 + 15 = 20$。
1: (1)
2: (1) (2)
3: (1)
4: (2) (2)
5: (1)
6: (2)
$4$ 颗技能 $1$ 装饰珠,$4$ 颗技能 $2$ 装饰珠。
$W_1(4) + W_2(4) = 5 + 15 = 20$。
Sample 2 Input
1 1
1 1
1 1
1 2
1 2
1 2
3
1 3 1 2 3
2 3 4 8 12
1 3 2 4 6
Sample 2 Output
18