2017"百度之星"程序设计大赛 - 资格赛 度度熊与邪恶大魔王

xiaoxiao2021-02-28  98

题目链接

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;//只要出现一个INF,就没办法消灭所有怪了 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
转载请注明原文地址: https://www.6miu.com/read-54867.html

最新回复(0)