题目链接
http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=774&pid=1003
题目大意
有n个怪， 每个怪都有血量ai和防御力bi， 你有m种技能， 每种技能有花费ki 和 伤害 pi 技能可以无限次释放 一个技能只能对一个怪物造成pi - bi点伤害 如果pi-bi<=0， 显然不能对怪物造成伤害， ai<=0时视怪物死亡 问你要把所有怪物打死最少花费
思路
显然需用dp 我们看数据范围 1<=n<=100000 1<=m<=1000 1<=a[i]<=1000 0<=b[i]<=10 0<=k[i]<=100000 0<=p[i]<=1000 这时我们可以设dp[t][j] 表示消灭护甲为t， 血量为j的怪最少花费 这就明显是一个完全背包问题了
代码
#include<bits/stdc++.h>
using namespace std;
const int INF =
0x3f3f3f3f;
struct P
{
int a, b;
}mon[
100005], cnt[
1005];
int dp[
15][
1005];
int main()
{
int n, m, mm =
0;
while(~
scanf(
"%d%d", &n, &m))
{
memset(dp, INF,
sizeof(dp));
for(
int i=
0; i<n; ++i)
{
scanf(
"%d %d", &mon[i].a, &mon[i].b);
mm = max(mm, mon[i].a);
}
for(
int i=
0; i<m; ++i)
scanf(
"%d %d", &cnt[i].a, &cnt[i].b);
for(
int t=
0; t<=
10; ++t)
{
for(
int i=
0; i<m; ++i)
{
for(
int j=
0; j<=mm; ++j)
{
if(j + t <= cnt[i].b) dp[t][j] = min(dp[t][j], cnt[i].a);
else dp[t][j] = min(dp[t][j], dp[t][j - cnt[i].b + t] + cnt[i].a);
}
}
}
long long ans =
0;
bool flag =
false;
for(
int i=
0; i<n; ++i)
{
if(dp[mon[i].b][mon[i].a] == INF)
{
flag =
true;
break;
}
ans += dp[mon[i].b][mon[i].a];
}
if(flag)
puts(
"-1");
else cout<<ans<<endl;
}
return 0;
}
反思
一开始我思路是用dp[i]表示造成i点伤害的最小花费， 这样想是因为我理解错了题目中的防御力， 防御力每次都能抵挡一部分伤害而我一开始把他当作了护甲（只能挡一次）。。。orz后来知道错误之后又想到用dp[i]表示花费i点法力值最大能造成多少伤害， 发现复杂度爆了最后队友提示之后我完全背包又写挫了， 一直以为滚动数组for的时候要逆序， 后来发现这样状态一直没法转移， 具体问题要具体分析， 不能太依赖模板了最后输出0的情况又写出bug， 一开始用ans>=INF判断输出0， bug是多个正确的消耗加起来之后会爆INF
