AOJ 2254 - 最短ルート - ツバサの備忘録

解法

制約を見ればbitDPと書いてあるのでbitDPをすることにします。
まず、 $i$ 番のステージをクリアした後に、再び $i$ 番目のステージを行くことは考えなくていいです。2回以上同じステージに行くことで得をすることはありません。
ということで、すでにクリアしたステージをビットで持つことを考えます。
クリアしたステージの集合を $S$ とします。

$dp[S] =$ 現在クリアしたステージが $S$ の状態のときに、ここからすべてのステージをクリアするまでにかかる時間の最小値

とします。初期値は $dp[S_{all}] = 0$ 、すなわち全てのステージをクリアした際、それ以降かかる時間は0ということです。
$dp[S]$ を埋めることを考えると、この状態から次に選ぶステージは、 $S$ の段階でまだビットが立っていないステージです。
そして、選べる装備は、すでにクリアステージのものなので、 $S$ の段階でビットが立っているステージ、もしくは装備なしです。
ということで、
$dp[S] = min(dp[\{S+i\}]+ t_{ij} )$ (ただし、 $i \not\in S$ , $j \in {0,S}$ )
となります。
あとはこれを計算すれば、 $dp[\varepsilon ]$ 、つまりまだ何もステージをクリアしていないときにかかる時間の最小値を参照すれば答えとなります。