TopCoder SRM 693 Div1 Easy BiconnectedDiv1

まだまだレートは下がる…。
https://community.topcoder.com/stat?c=problem_statement&pm=14331

問題

N個の頂点が左から順に一直線に並んでいる。
２つ隣の頂点同士は辺でつながっており、また１つ隣の頂点同士は辺でつながっている。
各辺は無向辺で、それぞれ重さが設定されている。

無向グラフにおいて２辺連結であるというのは、どの１辺を除いたとしても、２頂点間がまだ連結であるものという。
与えられたグラフを２辺連結である範囲で辺を減らすとき、残された辺の重さの総和の最小値を求めよ。

解法

２頂点i,(i+1)の間をまたがる辺は、(i-1,i+1),(i,i+1),(i,i+2)の３本である。
グラフが２辺連結であるためには２本の辺が必要なので減らせるのはこのうち１本までである。

左の頂点iから順に残す辺減らす辺を選んでいこう。
頂点(i,i+1)を跨ぐ辺を消すなら、以降はi+1以降の頂点からしか辺を消せないし、頂点(i,i+2)を跨ぐ辺を消すなら、以降はi+2以降の頂点からしか辺を消せない。
この考察をもとに消す辺の重さの総和をDPで最大化しよう。

class BiconnectedDiv1 {
	public:
	int minimize(vector <int> w1, vector <int> w2) {
		ll dp[105]={};
		for(int i=1;i<w1.size()-1;i++) dp[i+1]=max(dp[i+1],dp[i]+w1[i]), dp[i+2]=max(dp[i+2],dp[i]+w2[i]);
		return accumulate(w1.begin(),w1.end(),0)+accumulate(w2.begin(),w2.end(),0)-dp[w1.size()-1];
	}
}

まとめ

終わってみると数行のコードなんだよなぁ…。