TopCoder SRM 693 (Div. 1) BiconnectedDiv1
問題
i→i+1にコストw1[i]の辺を、i→i+2にコストw2[i]の辺を張ったグラフを考える。いくつかの辺を取り除いて作れる二重辺連結のグラフのうち、辺のコストの総和の最小値を求めよ。
二重辺連結とはどの辺を取り除いても連結なグラフのことである。
- 1≦n≦100
解法
頂点0の辺は両方使う必要がある。さて頂点1はどうなるだろうか。以下の3通りが考えられる。
一番最後のケースは最適となり得ない。なぜなら、このままだと(1,3)が橋になってしまうので、かならず(2,3)が必要になり、そうなると(1,2)が不要になるからである。
次は頂点 2 を決める。
1.2, 1.3 がダメなのは明らかで、2.3 が最適になり得ないのは(2,4)を橋にしないためには (3,4) が必要で、そうなると結局(2,3)が不要になるからである。
これをよく見ると、
- 状態1 のときは頂点 0 のときと同じ辺の選び方を迫られる
- 状態2 のときは頂点 1 のときと同じ辺の選び方を迫られる
ということが分かる。つまり状態を 2 つ持って DP すればうまくいく。
落ち着いて条件を整理すれば普通のDP。部屋で落ちる人が結構いたようで、写経ぐらいはすればよかったかもしれない。