Author: | Daniel Posdarascu |
Observations:
If we decide to cast a spell that will only add a poison stack on the enemy, do it as soon as possible. If we cast spells in such cases, it will be on the first moments that do not have a regeneration.
If we decide to cast a spell that will both add a poison stack and remove a regeneration one , again, do it as soon as possible when the regeneration is added. If we cast spells in such cases, it will be on the first moments that have a regeneration.
Obviously, we do prefer to cast a spell in case such that we will eliminate a regeneration while we add a poison, but some of those regenerations may be placed too late in the timeline, so it might not be optimal. In conclusion, the spells that we cast form a prefix in the timeline (first spells at moments from to ), plus some spells added at moments where regenerations are added.
Solution 1: compute for each moment from to the cost of improvement if you cast a spell at that time. If the moment has no regeneration spell added, then the cost of improvement is (N - x + 1) \cdot P because you only add a poison stack. If the moment does have a regeneration spell added at that time, the cost of improvement is (N - x + 1) \cdot (P + R) because you add a poison stack and also remove a regeneration one. Sort those options and select the best .
Solution 2: initially consider the full prefix of spells dealt at moments from to and then always take the last spell in case and see if it's better to change it with the first spell from case . This solution works in time proportional to the number of regeneration spells which is bounded by . This solution works for even higher constraints.