首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

2017百度之星资格赛:1003. 度度熊与邪恶大魔王

题目有点长,大意是说你有m种技能,每种技能的伤害是p[i],消耗水晶量为k[i];有n只怪兽,每只怪兽的生命值和防御力分别为a[i]和b[i]。每次释放技能怪兽的生命值会减少技能伤害减去怪兽防御力的差值  这道题乍看上去像是完全背包,因为每种技能可以重复施放,就像每种物品可以重复拿一样。但是我们发现防御力的数值范围是0到10,所以我们可以枚举防御力,这样就变成了个0-1背包,dpi的值表示杀掉一个生命值为i,防御力为j的怪物所需的最少晶石  那么对于每一种防御力i,枚举所有的生命值j(从1开始枚举),再枚举所有的技能l,如果这个技能一招刚好能打死这个怪物,就把dpj的值更新为min(dpj,k[l]);如果一招打不死,那么就把dpj的值更新为min(dpj,dp剩余血量 + k[l])  最终答案即为:∑i dp[a[i]][b[i]]

01
领券