Skip to content

14021: 【原4021】魔鬼杀手

题目

题目描述

author: Naïve Yan 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4021 

Description

现在,科学家小X一个人需要充当魔鬼杀手,用魔法打败这些魔鬼怪兽,从而带着秘密活着回去。

每个魔鬼怪兽都有一定的hitpoints,表示他们的生命值。科学家可以靠施魔法,降低魔鬼怪兽的hitpoints。每个魔法都会有一定的damage,表示会减少被攻击者damage的hitpoints。一个魔鬼怪兽被击败了当前仅当它的hitpoints <= 0。另一方面,魔法是要消耗魔力的,因为魔力是有限的,所以,科学家希望用最少的魔力击败所有的魔鬼怪兽。

请写一个程序,看他能否完成这个任务。

Input Format

输入数据按如下的格式给出:

N
HP1
HP2
…
HPN
M
Name1 MP1 Target1 Damage1
Name2 MP2 Target2 Damage2
…
NameM MPM TargetM DamageM

其中,N是魔鬼怪兽的数量(1 <= N <= 100)。Hpi表示第i个魔鬼怪兽的hitpoints(1 <= HPi <= 100000)。M表示可用的魔法数量(1 <= M <= 100)。Namej是第j种魔法的名字,最长会有30个大写或小写字母,MPj是这种魔法需要消耗的魔力(0 <= MPj <= 99)。Targetj要么是“Single”,要么是“All”,表示该魔法只攻击单个怪兽或对全体怪兽同时有效。Damagej表示对于所有攻击对象,可以减少攻击对象Damagej的hitpoints(0 <= Damagej <= 999999)。

所有数字都是整数,最少有一种魔法的 Damge 是非零的。

Output Format

输出一行一个整数,表示最小需要消耗的魔力。

Sample Input

3
8000
15000
30000
3
Flare 45 Single 8000
Meteor 62 All 6000
Ultimate 80 All 9999

Sample Output

232

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!