0, 1, ...., N とマスがあり、初期状態で主人公は0のマスに、モンスターはNのマスにいる。(1 <= N <= 10)
主人公は、HP_H、MP_Hのヒットポイントとマナポイントを持っている。 (2 <= HP_H <= 100, 1 <= MP_H <= 50)
モンスターはN_M体のHP_Mのモンスターの集合で、全体のHPは、N_M * HP_Mで表される。 (1 <= N_M, HP_M <= 10)
モンスターの残りHPがHの時、ceil(H/HP_M)のモンスターが生き残っていると考えることが出来る。
ゲームは、主人公のターン、モンスターのターン、と交互に進む。
主人公のターンでは、Lightning Bolt, Teleport, Healのうち、どれか一つの魔法を唱える。
魔法はどれもMPを1消費する。
Lightning Boltはモンスターにダメージを与える。
これはモンスターのいるマスによりダメージが変わる。
Teleportはモンスターを好きなマスにワープさせる。
Healは主人公のHPをdHだけ回復させる。(1 <= dH <= HP_H) しかし、主人公のHPの最大値はHP_Hで、これを超えて回復した分は切り捨てられる。
モンスターのターンでは、はじめに移動を行う。
モンスターは最大でVだけ、主人公の方に近寄ってくる。(1 <= V <= N)
主人公がいる為、モンスターはマス0には入れない。
移動の後、モンスターが主人公の隣のマスにいるならば、モンスターは主人公を攻撃できる。
モンスターの攻撃は、生き残っているモンスターの数に等しい数のダメージを主人公に与える。
N, HP_H, MP_H, HP_M, N_M, V, dHと、 Lightning Boltが与えるダメージのテーブルが与えられるので、
主人公が勝てる魔法の唱え方の一例を求めよ。
勝てないならば、DEFEATEDと表示せよ。
現在のターン * 主人公残りHP * モンスターの位置、の大きさのテーブルを用意する。
このテーブルに、この状態におけるモンスターのHPの最小値と、それを達成する為の前のターンの主人公の残りHP, モンスターの位置, 直前に唱えた魔法(Teleportなら移動位置も) を入れながらDPを行う。
計算量は、状態数*分岐数で、O(HP_N * MP_M * N^2)となる。