AOJ 2449 Connect

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2449

解法

これは典型問題です．
$i$ 行目の $j$ 番目に文字を置くかどうか考えた時に関係してくるのは，$i$ 行目の $1$ から $j - 1$ 列目と，$i - 1$ 行目の $j$ から $C$ 列目だけです．
なので結局，一行分の状態をビットで持つ bitDP にできます．

$dp[i][j][S] := i$ 行目の $j$ 列目まで見た時，文字が配置されている状況が $S$ であるときの最大値
$S$ の下位 $j$ ビットが今の行の状態，上位 $C - j$ ビットが直前の行の状態を表しています．

$i$ 行目 $j$ 列目の位置に文字を配置する場合，直前に同じ文字が置かれているかと，前の行の同じ列に同じ文字が置かれているかを見ます．
今配置しようとしている文字のインデックスは $bitcount(S \& (1 << j) - 1)$ で得られます．
上の行で配置されている文字のインデックスは，後ろから何番目であるかを考えれば，$|s_i| - bitcount(S >> j)$ で得られます．

使わない選択をする場合は，あとに配置できる余地が十分であるかを確認する必要があります．
その他，$S$ の状態でありえないものは適宜無視すればよいです．

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int R, C;
    cin >> R >> C;
    vector<string> s(R);
    for(int i = 0; i < R; ++i) {
        cin >> s[i];
    }
    vector<int> bitcount(1 << C);
    for(int i = 0; i < 1 << C; ++i) {
        bitcount[i] = __builtin_popcount(i);
    }

    vector<int> dp(1 << C, -1);
    dp[0] = 0;
    for(int i = 0; i < R; ++i) {
        for(int j = 0; j < C; ++j) {
            vector<int> nxt(1 << C, -1);
            for(int S = 0; S < (1 << C); ++S) {
                if(dp[S] == -1) {
                    continue;
                }
                int idx = bitcount[S & (1 << j) - 1];
                if(idx < s[i].size()) {
                    int t = dp[S];
                    if(idx > 0 && (S & 1 << (j - 1)) && s[i][idx - 1] == s[i][idx]) {
                        t++;
                    }
                    if(i > 0 && (S & 1 << j) && s[i][idx] == s[i - 1][s[i - 1].size() - bitcount[S >> j]]) {
                        t++;
                    }
                    nxt[S | 1 << j] = max(nxt[S | 1 << j], t);
                }
                if(C - j > s[i].size() - idx) {
                    nxt[S & ~(1 << j)] = max(nxt[S & ~(1 << j)], dp[S]);
                }
            }
            dp.swap(nxt);
        }
    }
    cout << 2 * *max_element(begin(dp), end(dp)) << endl;
}