AOJ 2443 Reverse Sort
解法
いろいろ嘘枝刈りBFSぽいことを考えましたが、全く解けませんでした…
↑こちらを参考にしました。
前から貪欲に揃えていくと、確実に回以内で揃える事ができます。
操作回数が増えると、たどり着ける状態が指数的に増えていきます。
なので、前(後ろ)からだけ見ていくのでは、最終的な状態が増えすぎてしまいます。
そこで、前から半分だけ、後ろから半分だけを見て、どちらからも行けるような状態が存在するかどうか、を調べます。
ということで、手だけ動かしてたどり着ける状態(と手数)を両方調べ、どちらにも存在する状態が無ければ
、そうでなければそれぞれの手数の和の最小値を求めればよいです。
感想
半分全列挙の経験があまりなかったので、面白かったです。勉強になりました。
