P1779 魔鬼杀手 题解&&思路

题目链接。

分析题目性质

我们发现假如有状态表示 \(M\) 个方案选或不选，那么这个状态有唯一确定的结果，即结果不会随着施法的顺序而改变。

考虑 \(dp.\)

我们从题目出发，发现每个方案有单个攻击或者集体攻击，想一想从这个方面考虑。

又由于每一个方案是可以选择无限次的，不难想到 完全背包。

思路

设 \(f_i\) 表示使用集体攻击造成伤害为 \(i\) 的最少魔力。

同时的，设 \(g_i\) 表示使用单个攻击造成伤害至少为 \(i\) 的最少魔力。

那么怎么统计呢？

我们可以采取先用集体攻击把怪打残，再用单个攻击补刀的方针（这个可以由题目性质得出）。

得出 \(f,g\) 之后，我们就可以考虑枚举 \(x\) 表示群体伤害为 \(x\)，然后计算出把每个怪兽补刀完的代价 \(y\)，最后的答案不难为：

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#define int long long
#define N 200005
#define M 105
using namespace std;
int n,m,a[M],mxai;
struct node{
	int cost,damage;
	bool type;
}dat[M];
int f[N],g[N];
signed main(){
	cin >> n;
	for (int i = 1;i <= n;i ++) cin >> a[i],mxai = max(mxai,a[i]);
	cin >> m;
	for (int i = 1;i <= m;i ++) {
		string s;
		cin >> s >> dat[i].cost >> s >> dat[i].damage;
		dat[i].type = (s == "All");
		if (dat[i].type && !dat[i].cost) return puts("0"),0;
		dat[i].damage = min(dat[i].damage,mxai);
	}
	for (int i = 1;i <= mxai;i ++) f[i] = g[i] = 1e17;//这里是为了防止后面相加的时候爆 long long.
	for (int i = 1;i <= m;i ++)
		if (dat[i].type)
			for (int j = dat[i].damage;j <= mxai;j ++)
				f[j] = min(f[j],f[j - dat[i].damage] + dat[i].cost);
	for (int i = 1;i <= m;i ++)
		if (!dat[i].type)
			for (int j = dat[i].damage;j <= mxai;j ++)
				g[j] = min(g[j],g[j - dat[i].damage] + dat[i].cost);
	for (int i = mxai - 1;i >= 0;i --) g[i] = min(g[i],g[i + 1]);
	int ans = 8e18;
	for (int i = 0;i <= mxai;i ++) {
		int res = f[i];
		for (int j = 1;j <= n;j ++)
			if (a[j] - i > 0)
				res += g[a[j] - i];
		ans = min(ans,res);
	}
	cout << ans;
	return 0;
}