mayoko’s diary

プロコンとかいろいろ。

AOJ 1320 City Merger

問題

City Merger | Aizu Online Judge

n 個の文字列が与えられる(それぞれの文字は 20 字以下)。これら n 個を連続部分文字列として含む文字列を作りたい。この文字列の最小の長さはいくらか。

解法

bitDP します。

dp[now][state] = (state にある文字列は作成済み, 今文字列の末尾は now に一致, という場合に残りの文字列の最小数) とします。

now の次につなげる文字を S[i] とすると, S[i] の末尾への重ね方は何通りか考えられます。また, 重ね方によっては, ついでにほかの文字列も生成できることがあるので, それも考慮します。

これを bitDP の中でついでにやっていると TLE したので, memo[n][i][j] = (S[n] の j 文字目から, S[i] を始めることができるか。できるなら, ついでに生成される文字列の集合) というのを前計算しておきます。

ところで, 上記の遷移ですが, 「S[i], S[j], S[k] をうまく組み合わせたら S[l] ができた」みたいなことがあるかもしれないから, 直前の文字だけを状態に持ってもダメなんじゃないかと思うかもしれません(僕もしばらくその可能性考えてウーンと言っていました)。ですが, そのような場合は S[i] の次に S[l] を置いたら S[j], S[k] ができた, という遷移で補えているので, 問題ありません。

後から「あっ, やべぇ」とおもうところがいろいろあってぐちゃぐちゃになったコード↓

const int MAXN = 16;
const int INF = 100000;
string S[MAXN];
int dp[MAXN][1<<MAXN];
int memo[MAXN][MAXN][22];
int N;

int dfs(int now, int state) {
    int& ret = dp[now][state];
    if (ret >= 0) return ret;
    if (state == (1<<N)-1) return ret = 0;
    ret = INF;
    int sz = S[now].size();
    for (int i = 0; i < N; i++) if (((state>>i)&1) == 0) {
        int isz = S[i].size();
        for (int j = max(0, sz+1-isz); j <= sz; j++) {
            int ok = memo[now][i][j];
            if (ok) {
                int nstate = state|ok;
                ret = min<int>(ret, (isz-(sz-j)) + dfs(i, nstate));
            }
        }
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (cin >> N) {
        if (N==0) break;
        for (int i = 0; i < N; i++)
            cin >> S[i];
        int ans = INF;
        memset(dp, -1, sizeof(dp));
        memset(memo, 0, sizeof(memo));
        for (int n = 0; n < N; n++) {
            int sz = S[n].size();
            for (int i = 0; i < N; i++) {
                int isz = S[i].size();
                for (int j = max(0, sz+1-isz); j <= sz; j++) {
                    const string s = S[n].substr(j);
                    const string t = S[i].substr(0, s.size());
                    if (s == t) {
                        const string u = s+S[i].substr(t.size());
                        int& ok = memo[n][i][j];
                        for (int k = 0; k < N; k++) {
                            if (u.find(S[k]) != string::npos) ok |= 1<<k;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < N; i++) {
            int state = 0;
            const string u = S[i];
            for (int j = 0; j < N; j++) {
                if (u.find(S[j]) != string::npos) state |= 1<<j;
            }
            ans = min<int>(ans, S[i].size() + dfs(i, state));
        }
        cout << ans << endl;
    }
    return 0;
}