问题 3251 --技能树(tuj1053)

3251: 技能树(tuj1053)

题目描述

  修罗王挖到“神话时代”的宝藏后,发现宝藏里的科技源可以看成是一棵技能树,一颗技能树的每个结点都是一项技能,要学会这项技能则需要耗费一定的技能点数。

只有学会了某一项技能以后,才能继续学习它的后继技能。每项技能又有着不同的级别,级别越高效果越好,而技能的升级也是需要耗费技能点数的。

现在修罗王已有一定的技能点数,他想尽可能地利用这些技能点数来达到最好的效果。因此他给所有的级别都打上了分,他认为效果越好的分数也越高。现在他要你帮忙寻找一个分配技能点数的方案,使得分数总和最高。

输入

该题有多组测试数据。
每组测试数据第一行是一个整数n(1≤n≤20),表示所有不同技能的总数。
接下来依次给出n个不同技能的详细情况。
每个技能描述包括5行。
第1行是该技能的名称。
第2行是该技能在技能树中父技能的名称,名称为None(以空一行表示))则表示该技能不需要任何的先修技能便能学习。
第3行是一个整数L(1≤L≤20),表示这项技能所能拥有的最高级别。
第4行共有L个整数,其中第I个整数表示从第I-1级升到第I级所需要的技能点数(0级表示没有学习过)。
第5行包括L个整数,其中第I个整数表示从第I-1级升级到第I级的效果评分,分数不超过20。
在技能描述之后,共有两行,第1行是一个整数P,表示目前所拥有的技能点数。
接下来1行是N个整数,依次表示角色当前习得的技能级别,0表示还未学习。这里不会出现非法情况。

输出

每组测试数据只需输出最佳分配方案所得的分数总和。

样例输入输出

输入#1 复制
3
Freezing Arrow
Ice Arrow
3
3 3 3
15 4 6
Ice Arrow
Cold Arrow
2
4 3
10 17
Cold Arrow
3
3 3 2
15 5 2
10
0 0 1
输出#1 复制
42

提示

序号 标题 作者 发表时间 费用 订购数 操作