team2012-D1-sol-0020

从 Trac 迁移的文章

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

原文章内容如下：

=== 题目大意 ===
有 n 个关卡, 每个关卡有一个怪物, 怪物有两种类型: 精英怪或是 boss. 精英怪是杂兵, 但是打赢一个精英怪可以获得 1 点祝福, 祝福必须达到 5 点才可以打 boss. 可以选择跳过 boss (即由你做决策). 打 boss 的时候是回合制: 在每个回合中, 由你先攻击, 然后 boss 攻击, 在一个回合内(任意时间)可以喝一次血瓶, 有无限的血瓶. 现在给出这 n 个关卡 (boss 的血量 hi 以及攻击力 di) , 然后再告诉你的血量 H, 攻击力 D, 血瓶恢复量 P. 问如何决策使得打倒的 boss 数量尽量多, 在这个基础上, 要求喝掉的血瓶尽量少. (明明都是无限的, 还节省什么啊 = =b)

=== 数据范围 ===
 * 1 <= n <= 50000
 * 1 <= hi <= 1000
 * 1 <= di <= 10
 * 1 <= H, D, P <= 1000

=== 解题思路 ===
这题显然是一个 DP, 如果去掉"喝掉的血瓶尽量少"这个要求, 那么就是一个经典的用单调队列优化的线性的 dp, 具体的大家可以看肥羊的解题报告. 再加上血瓶这个条件之后, 注意到数据范围里 boss 的攻击力异常的低下: 最多只有 10, 而且又是回合制的, 每个回合开始状态和前一个回合没有关系, 可以用 dp 解决. 再 check 一下数据范围: 最多是 1000 * 1000 * 10 (boss 血量 * 你的血量 * boss 攻击力). 而且 boss 是不能补血的, 所以有"boss 血量"这一维会递减. 于是一个三重循环转移一下就好了. 在读入之后先预处理一下打每个 boss 需要花费多少个血瓶. 注意可能打不过 boss, 在后面的 dp 中需要特判一下. 后面就是 for 一遍用单调队列维护一个单调递增(增 = 更优)的 boss 序列, 每次判断队首的 boss 和现在这个 boss 之间是否有 >= 5 个精英怪, 如果有的话, 就可以由这个转移过来.

题目大意

有 n 个关卡, 每个关卡有一个怪物, 怪物有两种类型: 精英怪或是 boss. 精英怪是杂兵, 但是打赢一个精英怪可以获得 1 点祝福, 祝福必须达到 5 点才可以打 boss. 可以选择跳过 boss (即由你做决策). 打 boss 的时候是回合制: 在每个回合中, 由你先攻击, 然后 boss 攻击, 在一个回合内(任意时间)可以喝一次血瓶, 有无限的血瓶. 现在给出这 n 个关卡 (boss 的血量 hi 以及攻击力 di) , 然后再告诉你的血量 H, 攻击力 D, 血瓶恢复量 P. 问如何决策使得打倒的 boss 数量尽量多, 在这个基础上, 要求喝掉的血瓶尽量少. (明明都是无限的, 还节省什么啊 = =b)

数据范围

• 1 <= n <= 50000
• 1 <= hi <= 1000
• 1 <= di <= 10
• 1 <= H, D, P <= 1000

解题思路

这题显然是一个 DP, 如果去掉"喝掉的血瓶尽量少"这个要求, 那么就是一个经典的用单调队列优化的线性的 dp, 具体的大家可以看肥羊的解题报告. 再加上血瓶这个条件之后, 注意到数据范围里 boss 的攻击力异常的低下: 最多只有 10, 而且又是回合制的, 每个回合开始状态和前一个回合没有关系, 可以用 dp 解决. 再 check 一下数据范围: 最多是 1000 * 1000 * 10 (boss 血量 * 你的血量 * boss 攻击力). 而且 boss 是不能补血的, 所以有"boss 血量"这一维会递减. 于是一个三重循环转移一下就好了. 在读入之后先预处理一下打每个 boss 需要花费多少个血瓶. 注意可能打不过 boss, 在后面的 dp 中需要特判一下. 后面就是 for 一遍用单调队列维护一个单调递增(增 = 更优)的 boss 序列, 每次判断队首的 boss 和现在这个 boss 之间是否有 >= 5 个精英怪, 如果有的话, 就可以由这个转移过来.