ferinの競プロ帳

競プロについてのメモ

AOJ2254 Fastest Route

Fastest Route | Aizu Online Judge

まずN<=8ならばnext_permutationi()でO(N!)全列挙すれば通りそう。クリアした順序は最短時間に関わらないので、どのステージをクリアしたかの情報のみを保持しておけば計算する量を減らせそう。クリアした・してないの2つの状態がNステージについてあるので全体で2^Nの状態について計算すればよさそう。

dp[S] = (集合Sをクリアするのにかかる最短時間)とする。
dp[S]は集合Sから要素を一つ取り除いた集合をクリアするのにかかる最短時間 + 集合から取り除いたステージをクリアするのにかかる最短時間と考えられるので漸化式で表すと
dp[S] = min{dp[S/{j}] + min{t[j][k] | k∈S/{j}} | j∈S}
となる。集合について扱うDPなのでbitDPで書くとO(n^2・2^n)で解けて間に合う。