01-11 01:15 外交学院 C++ 发布于广东
关注
牛客周赛 round75 E
#牛客创作赏金赛#
题意:n个英雄花费ai，战斗力bi，其中有些英雄同时上场有额外战斗力加成，问在不超过cost花费能到的最高战斗力，且只能上最多4个英雄，一个英雄只会有一种关系同时上场有额外战斗力加成
思路:观察到数据很小，且如果没有额外战斗力加成就是普通的01背包dp啊，所以由此思路我们可以继续往背包dp方向想，只要把双生英雄先预处理分成一组，即预处理出4种情况xy同时上场 ，x上y不上，x不上y上，xy都不上，还有单独没有关系的英雄z，为两种情况，z上，z不上。设dp[n][m][k]为前n组花费m上了k个英雄的最大战斗力跑01分组dp即可
题意:n个英雄花费ai，战斗力bi，其中有些英雄同时上场有额外战斗力加成，问在不超过cost花费能到的最高战斗力，且只能上最多4个英雄，一个英雄只会有一种关系同时上场有额外战斗力加成
思路:观察到数据很小，且如果没有额外战斗力加成就是普通的01背包dp啊，所以由此思路我们可以继续往背包dp方向想，只要把双生英雄先预处理分成一组，即预处理出4种情况xy同时上场 ，x上y不上，x不上y上，xy都不上，还有单独没有关系的英雄z，为两种情况，z上，z不上。设dp[n][m][k]为前n组花费m上了k个英雄的最大战斗力跑01分组dp即可
全部评论
相关推荐
顺丰集团工作强度 372人发布 
smile丶snow：尽量保证的一张a4纸吧。为什么工作经历只有公司？如果项目经历是工作里面的，应该写到工作经历里的吧。没有写项目职责，项目全是一个人写的吗？标题大小也好怪。两个项目的分割看不出来是，它和那些项目成功字体是一样大的 点赞 评论 收藏
分享