zrj2012-B3-0020

从 Trac 迁移的文章

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

原文章内容如下：

题目大意：有若干怪物，其中一些是精英怪，一些是BOSS，每杀死一个精英怪，你会得到一个buff，buff最多可以累积5个，多了也没用。玩家只有在升上恰好有5个buff时，才会去打boss，不然他会跳过。每个Boss有一个生命值和攻击力，玩家也有一个生命值和攻击力。
玩家可以秒杀任何精英怪，但是面对boss时，他与Boss进行回合战，每一回合，他先攻，然后boss攻击，如果玩家攻击后boss死了，boss就不会继续攻击。此外，玩家可以喝药，一瓶药可以补充定量的hp，但是hp（生命值）不能超过初始生命值，即初始生命值同时也是上限，超出部分就浪费了。同时一回合只能喝一瓶药，但可以在这一回合任意时刻（boss攻击前或boss攻击后）喝，药的总量无限。
现在问你，最多能够打多少boss，在此基础上，最少要喝多少药。
这题主要是要算一下打每个Boss需要喝的药的数量。我一开始是想用贪心的，但是贪心相当不好写，其中要分许多情况。
还有一个做法，是标程的做法：f[i][j][k]表示英雄血量是i，boss血量是j，boss攻击力是k的情况下，最少用了多少血瓶，然后dp转移。由于Boss血量是递减的（被玩家攻击），因此可以直接dp。

题目大意：有若干怪物，其中一些是精英怪，一些是BOSS，每杀死一个精英怪，你会得到一个buff，buff最多可以累积5个，多了也没用。玩家只有在升上恰好有5个buff时，才会去打boss，不然他会跳过。每个Boss有一个生命值和攻击力，玩家也有一个生命值和攻击力。

玩家可以秒杀任何精英怪，但是面对boss时，他与Boss进行回合战，每一回合，他先攻，然后boss攻击，如果玩家攻击后boss死了，boss就不会继续攻击。此外，玩家可以喝药，一瓶药可以补充定量的hp，但是hp（生命值）不能超过初始生命值，即初始生命值同时也是上限，超出部分就浪费了。同时一回合只能喝一瓶药，但可以在这一回合任意时刻（boss攻击前或boss攻击后）喝，药的总量无限。

现在问你，最多能够打多少boss，在此基础上，最少要喝多少药。

这题主要是要算一下打每个Boss需要喝的药的数量。我一开始是想用贪心的，但是贪心相当不好写，其中要分许多情况。

还有一个做法，是标程的做法：f[i][j][k]表示英雄血量是i，boss血量是j，boss攻击力是k的情况下，最少用了多少血瓶，然后dp转移。由于Boss血量是递减的（被玩家攻击），因此可以直接dp。