Algoogle

Algorithm for Programming Contest

AOJ 1320 City Merger

Category: AOJ Tag: dp

CityMerger

問題概要


複数の文字列が与えられるので, それらの共通部分を重ねるようにまとめて1つの文字列にしたい.
そのときの最小の長さを求めよ.

解法


つなげるのは前後で一致しているか完全に含んでいる場合のみ.
完全に含んでいる場合は含まれるは明らかにいらないので始めに除外しておく.
あとはどの順番に繋げていくかだけなのでbitDPすればよい.
dp[S][u] := 既に使った文字列の情報Sと最後に使った文字列がuのときの最小の長さ

コード


(1320.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
#define all(u) begin(u),end(u)
#define pb push_back
const int inf = 1e9;

int N;
string inp[16];
vector<string> names;
int tail[16][16];
int dp[1<<14][16];

void mymin(int &a, int b){
    if(a == -1) a = b;
    else a = min(a, b);
}

int solve(){
    bool use[16];
    memset(use,-1,sizeof(use));
    rep(i,N) rep(j,N)
        if(i != j and use[j] and inp[j].find(inp[i]) != string::npos)
            use[i] = 0;
    names.clear();
    rep(i,N) if(use[i]) names.pb(inp[i]);
    N = names.size();
    rep(i,N) rep(j,N) if(i != j){
        int n = names[i].size(), m = names[j].size();
        for(int k = min(n, m); k >= 0; k--)
            if(names[i].substr(n-k,k) == names[j].substr(0,k)){
                tail[i][j] = m-k;
                break;
            }
    }
    memset(dp,-1,sizeof(dp));
    rep(i,N) dp[1<<i][i] = names[i].size();
    rep(S,1<<N) rep(u,N) if(S&(1<<u))
        rep(v,N) if(!(S&(1<<v)))
            mymin(dp[S|(1<<v)][v], dp[S][u]+tail[u][v]);
    int ans = inf;
    rep(i,N) mymin(ans, dp[(1<<N)-1][i]);
    return ans;
}

bool input(){
    cin >> N;
    if(!N) return 0;
    rep(i,N) cin >> inp[i];
}
signed main(){
    while(input()){ cout << solve() << endl;}
    return 0;
}

Comments