1549

8角形の板が複数個与えられる。各辺には色が塗られている。好きな順番に好きな角度回転させて一列に並べるとき、隣接する辺は同じ色でなくてはならない。また隣接は循環する。各色に点数が与えられているとき、隣接する辺に塗られている点数の合計値のうち最小のものを答えよ、という問題。

典型的なメモ付き探索問題。最初の辺(循環するので)と今までの最後の辺と使った板を状態として探索するだけ。(当然ながら)うまく書けばDPになる。

DPの方が綺麗に書けるような気がしてきた...。