hotpepsiの練習帳

SRM 693

23:54

https://competitiveprogramming.info/topcoder/srm/round/16748/div/1

Div1 Easy (250) BiconnectedDiv1

問題

• 任意の頂点u,vについて、任意の辺eを取り除いてもuからvに到達可能なグラフを、2辺連結グラフと呼ぶ
• N個の頂点が与えられる
• 頂点iとi+1には重みw1[i]の辺がある
• 頂点iとi+2には重みw2[i]の辺がある
• 2辺連結グラフを維持しながら、辺を除去するとき、重みの合計の最小値を求める

方針

• DPでできそう
• ある頂点の状態として、入ってくる辺と、出ていく辺と、その頂点を追い越して次の頂点に接続している辺がある
• 制約条件は、必ず2辺以上を持つこと
• 最初の頂点は必ず2辺が出ていく(自分を追い越す辺はない)
• 最後の頂点は必ず2辺が入る(自分を追い越す辺はない)
• dp[頂点][辺の状態]＝コスト として、辺をつないでいない状態からスタートし、1頂点ずつ処理していく
• 自分に2辺接続していたら(2つ前か一つ前の頂点から辺が出ていたら)、出ていく辺の本数は任意
• 自分に1辺接続していたら、1または2本の辺を出す
• 前の頂点から辺がなければ、2本の辺を出す
• Passed System Test
• (終了後)
• 複数の場合をまとめた
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_693/BiconnectedDiv1.cpp

結果

o-- 99.77pt 160th/373 rating 1429 -> 1478 (+49)

DP書くのに1時間くらいかかったが、4連続0点から脱出できた。

http://togetter.com/li/991988