TopCoder Open 2014 Round1A Hard EllysLamps

問題

n個のランプとn個のスイッチがあり、それぞれ一列に並んでいる。
i番目のスイッチを押すと、i番目のランプのオンオフが入れ替わる他、
i-1番目のランプのオンオフが入れ替わる可能性があり、
i+1番目のランプのオンオフが入れ替わる可能性がある。

どのランプとスイッチが対応するかは最初に決まっており、操作の途中で変わることはない。
ランプの初期状態が与えられたとき、（スイッチの対応はわからない）
ついているランプの個数を最小になるように操作をしたとき、
最悪でも残ってしまうランプの個数を求めよ。
操作は何回でもおこなってよい。
すなわち、どのランプとスイッチが対応しているかは操作者は知ることができる。

制約条件

n≦50

方針

editorial（https://docs.google.com/document/d/1O5v5d_iY9zV0slI8fgKhZosDsYDNSZVsOXeL2Cui0DM/pub）見た。

最善の操作をしたときに最悪でいくつのランプが残るかなので、ちょっと変わったDP.
スイッチを左から順に見ていく。
dp[pos][posの場所のランプがついているか][posを押したときに増えるランプ][posを押さなかったときに増えるランプ]

というDP.
posを押したときに増えるランプ、押さなかったときに増えるランプの個数は、
状態遷移を、うまくやると確定させることができる。
(posのスイッチがpos+1のランプにつながっているか)と
(pos+1のスイッチがposのランプにつながっているか)で場合わけをすればよい。

pos+1のスイッチがposのランプにつながってないときは、
posのランプの点灯状態が、次のスイッチを押す押さないにかかわらず、コストになる。
つながっているときは、
posのランプの点灯は、次のスイッチを押す押さないで反転するので、そういう風にコストをつける。

ソースコード

int n;
int dp[51][2][2][2];
bool L[50];

int rec(int pos, int lit, int use, int notuse){
	
	int &res = dp[pos][lit][use][notuse];
	if(res >= 0) return res;
	
	if(pos == n - 1) return res = min(lit + notuse, !lit + use);
	
	rep(left, 2) rep(right, 2){
		res = max(res, min(
			//click pos
			rec(pos + 1, L[pos + 1] ^ right, lit ^ 1 ^ left, lit ^ 1) + use,
			//not click
			rec(pos + 1, L[pos + 1], lit ^ left, lit) + notuse
		));
	}
	return res;
}

class EllysLamps {
	public:
	int getMin(string lamps) {
		
		n = lamps.size();
		rep(i, n) L[i] = lamps[i] == 'Y';
		memset(dp, -1, sizeof(dp));
		return rec(0, L[0], 0, 0);
	}
};