AOJ 2449 Connect

問題

n個の単語をそれぞれ一行に1つずつ書く。
幅wになるように、自由にスペースを入れることができる。

スペースを入れた後で、上下左右に同じ文字が隣り合っているとき（スペースを挟んではいけない）、１点を得るものとする。
得られる得点の最大値を求めよ。

制約条件

n≦128, w≦16

方針

よくある1行ずつ覚えるbitDP
bitのうち最初のj個は今の行で、残りのw - j個は上の行の状態を覚える。

dp[i][j][bit]を、i行j列までで、今の状態がbitであるときの得点の最大値とする。
これを、j番目に文字を入れるかスペースを入れるかで更新するDPをすればいい。

配列は使いまわせる。

ソースコード

int n, w;
int dp[2][1 << 16], bc[1 << 16];
string in[130];

int main(){
	cin >> n >> w;
	rep(i, n) cin >> in[i];
	rep(i, 1 << w) bc[i] = __builtin_popcount(i);
	
	memset(dp, -1, sizeof(dp));
	dp[0][0] = 0;
	
	int cur = 0, next = 1;
	rep(i, n) rep(j, w){
		memset(dp[next], -1, sizeof(dp[next]));
		
		rep(bit, 1 << w) if(dp[cur][bit] >= 0){
			//i行の単語の、今何文字目かは、j以下のbitを見ればわかる
			int idx = bc[bit & (1 << j) - 1];
			
			if(idx < in[i].size()){
				int nxt = dp[cur][bit];
				//一つ前の文字と一致するか
				if(j && (bit & 1 << (j - 1)) && in[i][idx - 1] == in[i][idx]) nxt++;
				
				//一つ上の文字と一致するか。
				//一つ上の文字が何であるかは、ビットのjより大きい部分を見ればわかる
				if(i && (bit & 1 << j) && in[i][idx] == in[i - 1][in[i - 1].size() - bc[bit >> j]]) nxt++;
				dp[next][bit | 1 << j] = max(dp[next][bit | 1 << j], nxt);
			}
			if(idx + w - j > in[i].size()){
				dp[next][bit & ~(1 << j)] = max(dp[next][bit & ~(1 << j)], dp[cur][bit]);
			}
		}
		swap(cur, next);
	}
	cout << 2 * *max_element(dp[cur], dp[cur] + (1 << w)) << endl;
	
	return 0;
}