Jumping monkey (UVa Live Archive Europe Southwestern 2010)
問題
n頂点のグラフが与えられる。そこの頂点のどこかに猿がいるので撃ち殺したい。猿を殺すために銃を撃つと、猿がそこに居なかった場合は猿は必ず隣接する頂点のどこかに移動する。
1<=n<=21
解法
bitDPで解く。遅かったんでmemsetを使う分だけしたり、閉路があるとNOを返すとかで高速化した。
n頂点のグラフが与えられる。そこの頂点のどこかに猿がいるので撃ち殺したい。猿を殺すために銃を撃つと、猿がそこに居なかった場合は猿は必ず隣接する頂点のどこかに移動する。
1<=n<=21
bitDPで解く。遅かったんでmemsetを使う分だけしたり、閉路があるとNOを返すとかで高速化した。