洛谷P1779 魔鬼杀手

传送门

题目描述

你生活在一个怪兽世界里。你需要用魔法反抗这些怪兽。

每个怪兽都有一定的 hit points，表示他们的生命值。你可以靠施魔法，降低怪兽的 hit points。每个魔法都会有一定的 damage，表示会减少被攻击者 damage 的 hit point。一个怪兽被击败了当前仅当它的 hitpoint 小于等于 0。另一方面，魔法是要消耗魔力的。因为你的魔力是有限的，你希望用最少的魔力击败所有的怪兽。写一个程序完成这个任务。

输入格式

输入按如下的格式给出：

NN
HP_1HP
1
​

HP_2HP
2
​

…
HP_NHP
N
​

MM
Name_1Name
1
​
MP_1MP
1
​
Target_1Target
1
​
Damage_1Damage
1
​

Name_2Name
2
​
MP_2MP
2
​
Target_2Target
2
​
Damage_2Damage
2
​

…
Name_MName
M
​
MP_MMP
M
​
Target_MTarget
M
​
Damage_MDamage
M
​

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

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

输出格式

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

输入输出样例

输入 #1复制
3
8000 15000 30000
3
Flare 45 Single 8000
Meteor 62 All 6000
Ultimate 80 All 9999
输出 #1复制
232

上代码：

#include 
using namespace std;
int n, m, a[105], b[105], c[105];
long long res, ans = (long long)1 << 50, f[2000005], g[2000005];
bool u[105];// 群体攻击还是个体攻击 
string s, t;
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]);// 怪的血量 
	scanf("%d", &m);
	for(int i = 1; i <= m; i++)
	{
		cin >> s >> b[i] >> t >> c[i];
		if(t == "All")// 标记为群体攻击 
			u[i] = 1;
		if(!b[i] && c[i]) // 免费的午餐 
		{
			printf("0\n");
			return 0;
		}
		c[i] = min(c[i], 200000);// 稍微削减伤害 
	}
	for(int i = 1; i <= 200000; i++)
		f[i] = g[i] = (long long)1 << 50;// 初始化 
	for(int i = 1; i <= m; i++)// 群体攻击 
	{
		if(u[i])
		{
			for(int j = c[i]; j <= 200000; j++)
				f[j] = min(f[j], f[j - c[i]] + b[i]);
		}
	}
	for(int i = 1; i <= m; i++)// 个体攻击 
	{
		if(!u[i])
		{
			for(int j = c[i]; j <= 200000; j++)
			{
				g[j] = min(g[j], g[j - c[i]] + b[i]);
			}
		}
	}
	for(int i = 199999; i >= 0; i--)// 逆序转移 
	{
		if(g[i] > g[i + 1])
			g[i] = g[i + 1];
	}
	for(int i = 0; i <= 200000; i++)// 枚举群体攻击伤害 
	{
		res = f[i];
		for(int j = 1; j <= n; j++)
		{
			if(a[j] - i > 0)// 个体攻击补刀 
				res += g[a[j] - i];
		}
		ans = min(ans, res);
	}
	printf("%lld\n", ans);// 愉快输出 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62