TopCoder SRM 693 (Div. 1) BiconnectedDiv1

問題

i→i+1にコストw1[i]の辺を、i→i+2にコストw2[i]の辺を張ったグラフを考える。いくつかの辺を取り除いて作れる二重辺連結のグラフのうち、辺のコストの総和の最小値を求めよ。

二重辺連結とはどの辺を取り除いても連結なグラフのことである。

  • 1≦n≦100

解法

頂点0の辺は両方使う必要がある。さて頂点1はどうなるだろうか。以下の3通りが考えられる。

f:id:pekempey:20160626123008p:plain

一番最後のケースは最適となり得ない。なぜなら、このままだと(1,3)が橋になってしまうので、かならず(2,3)が必要になり、そうなると(1,2)が不要になるからである。

次は頂点 2 を決める。

f:id:pekempey:20160626122747p:plain

1.2, 1.3 がダメなのは明らかで、2.3 が最適になり得ないのは(2,4)を橋にしないためには (3,4) が必要で、そうなると結局(2,3)が不要になるからである。

これをよく見ると、

  • 状態1 のときは頂点 0 のときと同じ辺の選び方を迫られる
  • 状態2 のときは頂点 1 のときと同じ辺の選び方を迫られる

ということが分かる。つまり状態を 2 つ持って DP すればうまくいく。

gist.github.com

落ち着いて条件を整理すれば普通のDP。部屋で落ちる人が結構いたようで、写経ぐらいはすればよかったかもしれない。