KUPC2013 : C - チョコレート

さてC。まだこのあたりは何とか。
http://kupc2013.contest.atcoder.jp/tasks/kupc2013_c

問題

N×Mマスで構成された板チョコがある。
各マスは、上に他のチョコが無く、左右どちらかにスペースがあれば食べることができる。
各マスは甘いか辛いかのどちらかであり、あるマスのチョコを食べると、残った上下左右のマスの甘い辛いが反転する。

甘いセルを食べられる最大数を答えよ。

解法

１行目を全部食べ、２行目を全部食べ…と上から順に食べることを考える。
２行目以降は上の行を食べる際に甘い辛いが反転する。

後は、行単位で甘いチョコを食べる列を最大化すればよい。
チョコは左から食べるか右から食べるかしかないので、どこまで左から食べて残りを右から食べるか、を幅M通りだけ試せばよい。
両端以外は両隣を食べる際に甘い辛いが反転することに注意。

１列当たりO(M^2)、全体でO(NM^2)で処理できる。

int W,H;
int A[101];

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty;
	
	cin>>H>>W;
	int ns=0;
	FOR(y,H) {
		FOR(x,W) A[x]=GETi()^(y>0);
		int ma=0;
		FOR(x,W) {
			j=0;
			FOR(i,W) j+=A[i]^(i!=x)^(i!=0)^(i!=W-1);
			ma=max(ma,j);
		}
		ns += ma;
	}
	_P("%d\n",ns);
}

まとめ

最初メモ再帰で左と右どちらか食べるか全通りチェックしていたが、こっちの方が楽だな。