SRM658 div2 500

とぷこだ 過去問

問題

敵機がN機いる。
各敵機はHP[i]で、1ターンの攻撃で最大3機までに対し、以下のような攻撃を行える。
・最初のターゲットには9ダメージを与える
・次のターゲットには6ダメージを与える
・最後のターゲットには1ダメージを与える
HP[i]が0以下になった敵機は破壊される場合、すべての敵機を破壊するのに必要な最低ターン数を答える。


1<=N<=3
HP[i]<=60

考え方

全探索を考える。


3機までしかないので、どのように攻撃するかは6通りしかない。
また、敵HPは60までしかないので、状態が60^3=216,000程度しかない。
なので、BFSでメモしながら全状態を確かめてあげれば最短手順がでる。