TopCoder SRM 583 Div1 Medium TurnOnLamps

問題

n頂点からなる無向木が与えられる。
各辺には重要か重要でないかと、初期状態でオンかオフかが与えられる。

木の二頂点を選び、その頂点を結ぶ最短パス上にある辺全てのオンオフを入れ替えるという操作を繰り返し、
重要な辺全てをオンであるようにしたい。

必要な操作の回数の最小値を求めよ。

制約条件

n≦50

方針

いつもの、パスは重ならないものと考えてよい系のDP.
グラフが木なので、二つのパスが重なるとき、重なった部分がもともとなかったものとして、別々の二つのパスを取ったとしてもよい。

なので、重ならないパスを取る問題になる。

あとはDPすればよくて、
dp[pos][posから親へパスが伸びているか]:=最小コスト
を更新していけばよい。

各頂点でもう一度DPを行う必要がある。
（たしかこれは配列をポインタとして子に渡していくDPをすればオーダーが落ちる形だった気がしたけど、サイズが小さいのでどうでもいい）

下のコードではrep(j, 2) rep(k, 2) rep(l, 2) rep(m, 2)の部分で、
dp[child][j]を更新していく。childはいま何番目の子を見ているか、
jは一本パスがあまっているか。
mは子から余ったパスが伸びているか、lはその辺を反転させるか。
mとlが異なる場合、子から新規にパスを伸ばさなければならないのでコスト+1
kはパスを親まで伸ばすか。
kとlが異なる場合またコストが1かかる。

で、あまったパスと結べる場合は、パスのコストが一個へる。

実は貪欲にパスを取るだけで通る問題らしかった。わろす。

ソースコード

#define F first
#define S second

int n;
vector<pair<int, pi> > e[60];

int dp[60][2];

void rec(int c, int p){
	
	int child = 0;
	int dp2[60][2];
	
	rep(i, 60) rep(j, 2) dp2[i][j] = inf;
	dp2[0][0] = 0;
	dp2[0][1] = 1;
	
	rep(i, e[c].size()) if(e[c][i].F != p){
		
		rec(e[c][i].F, c);
		rep(j, 2) rep(k, 2) rep(l, 2) rep(m, 2){
			
			if(e[c][i].S.S && (e[c][i].S.F ^ l) == 0) continue;
			int cost = dp2[child][j] + dp[e[c][i].F][m];
			
			if(l != m) cost++;
			if(k != l) cost++;
			if(j && k) cost--;
			
			dp2[child + 1][j ^ k] = min(dp2[child + 1][j ^ k], cost);
		}
		child++;
	}
	rep(i, 2) dp[c][i] = dp2[child][i];
}

class TurnOnLamps {
	public:
	int minimize(vector <int> roads, string initState, string isImportant) {
		
		rep(i, 60) rep(j, 2) dp[i][j] = inf;
		
		n = roads.size() + 1;
		rep(i, n) e[i].clear();
		rep(i, n - 1){
			e[i + 1].pb(mp(roads[i], mp(initState[i] - '0', isImportant[i] - '0')));
			e[roads[i]].pb(mp(i + 1, mp(initState[i] - '0', isImportant[i] - '0')));
		}
		
		rec(0, 0);
		
		return dp[0][0];
	}
};