AOJ 1140 : Cleaning Robot

Cleaning Robot | Aizu Online Judge

巡回セールスマンライクな問題。汚れの数が最大10なのでbitDPで解くことが予想できる。

bitDPが分からない場合、以下の資料が大変参考になる。

プログラミングコンテストでの動的計画法

あらかじめ汚れにインデックスを振っておき、
各汚れ間に何回の移動で到達できるか幅優先探索しておく。
便宜上、ロボットの初期位置も汚れとして扱うと楽。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2352824#1

これに似た問題で、AOJ 0245 Time Sale(タイムセール)がある。
PCK2011予選の問題だけど、こちらの方が難しめなのでオススメ。

arukuka.hatenablog.com