tkdsheep-solution-0020

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
大菠萝3

首先如果不考虑血瓶消耗，那么题目就是一个很简单的dp

dp[i]表示前i个地图能收获的最大装备数

如果第i个地图没有boss，那么dp[i]=dp[i-1]; 如果有boss，则分两种情况，打boss或者跳过boss 则dp[i]=max(dp[i-1],dp[j]+1) 
这里的j是从i往左扫，距离i最近的且i和j之间有5只精英怪的地图，这个扫的过程最好不要直接枚举扫过去，否则遇到特殊的数据容易超时，比较好的做法是类似并查集之类的

然后boss站有一个血瓶消耗，要在最大装备的前提下，总血瓶消耗尽量小，所以如果知道每个boss的血瓶消耗，前面的dp只需改成双关键字比较即可

而每个boss的血瓶消耗有2种做法，一种是对每个boss都用分类讨论的贪心做法，不过这个贪心很难写对，因为中间过程会发生转变，出题人、验题人、做题人都没有写出来。。所以先放弃。。囧

另外一个做法是用dp直接预处理出英雄血量多少、boss血量多少、boss攻击力多少的情况下，需要消耗多少血瓶

即dp[i][j][k]，i表示英雄当前血量，j表示boss当前血量，k表示boss攻击力

因为每回合boss的血一定是减少的，所以把boss血量作为第一层循环即可满足最优子结构，转移的时候分2种情况

再boss攻击之前喝血瓶，注意生命不能超过最大上限再boss攻击之后喝血瓶，注意boss如果打死英雄了就不能喝血瓶了，同样生命也不能回复超过上限
}}}

大菠萝3
首先如果不考虑血瓶消耗，那么题目就是一个很简单的dp
dp[i]表示前i个地图能收获的最大装备数
如果第i个地图没有boss，那么dp[i]=dp[i-1]; 如果有boss，则分两种情况，打boss或者跳过boss 则dp[i]=max(dp[i-1],dp[j]+1) 
这里的j是从i往左扫，距离i最近的且i和j之间有5只精英怪的地图，这个扫的过程最好不要直接枚举扫过去，否则遇到特殊的数据容易超时，比较好的做法是类似并查集之类的
然后boss站有一个血瓶消耗，要在最大装备的前提下，总血瓶消耗尽量小，所以如果知道每个boss的血瓶消耗，前面的dp只需改成双关键字比较即可
而每个boss的血瓶消耗有2种做法，一种是对每个boss都用分类讨论的贪心做法，不过这个贪心很难写对，因为中间过程会发生转变，出题人、验题人、做题人都没有写出来。。所以先放弃。。囧
另外一个做法是用dp直接预处理出英雄血量多少、boss血量多少、boss攻击力多少的情况下，需要消耗多少血瓶
即dp[i][j][k]，i表示英雄当前血量，j表示boss当前血量，k表示boss攻击力
因为每回合boss的血一定是减少的，所以把boss血量作为第一层循环即可满足最优子结构，转移的时候分2种情况
再boss攻击之前喝血瓶，注意生命不能超过最大上限再boss攻击之后喝血瓶，注意boss如果打死英雄了就不能喝血瓶了，同样生命也不能回复超过上限