プログラミングコンテストチャレンジブック 3-4, 3-5
再開します。第3章 3-4 の途中からです。
- バケット法と平方分割
- セグメント木でも(より効率的に)実現可能
次に 3-5 動的計画法を極める! に進みます
- 巡回セールスマン問題
- 漸化式を立式
- dp[V][0] = 0
- dp[S][v] = min{dp[S + {u}][u] + d(v,u) | u is not included by S}
- 添字の集合をビットで表現
- ビットDP
- 漸化式を立式
- Travelling by Stagecoach
- グラフの移動のかかるコストの計算だけど経路だけじゃなくてチケット(輸送力が違う)も移動コストに関係する。おもしろい
- 単純に都市をノードにするグラフではなくて、残りチケットなどを含めた「状態」をノードにすることでグラフを構築して解く
- チケットの枚数が少ない(1<=n<=8)のでグラフの構築はそんなに重くない
- ドミノ敷き詰め
