競技プログラミング用 知識集積所
ABC410E - Battles in a Row
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
単純に考えると
- i番目のモンスターを、体力j、魔力kの状態から倒せるか
で三次元に動的計画法（未作成）をしたくなるが、それぞれ上限が3000なので時間制限やメモリが厳しい。
そこで、変数は2つにして、
そこで、変数は2つにして、
- i番目のモンスターを、体力j、状態から倒すのに魔力がどれだけ必要か
- i番目のモンスターを、魔力j、状態から倒すのに体力がどれだけ必要か
- 体力j、魔力kの状態からモンスターを何体まで倒せるか
というような形で組むことで間に合わせる。
