AOJ 1320 - City Merger

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

概要

n 個の名前が与えられ，それらすべてをマージしてできる名前の長さの最小値を答える．

例えば FUKUOKA, OKAYAMA, YAMAGUCHI の3つをマージしてできる最小の長さの名前は FUKUOKAYAMAGUCHI である．

制約

解法

まず，他の名前の部分文字列になっているような名前は考慮しなくてよいので除外する．

あとは i 番目の名前の後ろに j 番目の名前をマージしたときに被る文字列の長さを予め計算しておき， 巡回セールスマン問題の要領で今までに使った名前の状態と最後に使った名前でビット DP すればよい．

  1 #include <iostream>
  2 #include <vector>
  3 #include <algorithm>
  4 using namespace std;
  5 
  6 struct kmp
  7 {
  8   string pat;
  9   int len;
 10   vector<int> tbl;
 11   kmp(const string& s) : pat(s), len(s.size()), tbl(s.size())
 12   {
 13     tbl[0] = -1;
 14     tbl[1] = 0;
 15     for (int i = 2, j = 0; i < len;) {
 16       if (pat[i-1] == pat[j]) {
 17         tbl[i] = j+1;
 18         i++; j++;
 19       } else if (j > 0) {
 20         j = tbl[j];
 21       } else {
 22         tbl[i] = 0;
 23         i++;
 24       }
 25     }
 26   }
 27 
 28   pair<bool,int> search(const string& s) const
 29   {
 30     const int L = s.size();
 31     int i = 0;
 32     for (int m = 0; m+i < L;) {
 33       if (pat[i] == s[m+i]) {
 34         i++;
 35         if (i == len) {
 36           return make_pair(true, m);
 37         }
 38       } else {
 39         m = m + i - tbl[i];
 40         if (i > 0) {
 41           i = tbl[i];
 42         }
 43       }
 44     }
 45     return make_pair(false, i);
 46   }
 47 };
 48 
 49 int main()
 50 {
 51   int N;
 52   while (cin >> N && N != 0) {
 53     vector<string> v;
 54     for (int i = 0; i < N; i++) {
 55       string s;
 56       cin >> s;
 57       v.push_back(s);
 58     }
 59     vector<kmp> cities;
 60     for (int i = 0; i < N; i++) {
 61       kmp k(v[i]);
 62       for (int j = 0; j < N; j++) {
 63         if (i != j && k.search(v[j]).first) {
 64           goto SKIP;
 65         }
 66       }
 67       cities.push_back(k);
 68 SKIP:
 69       ;
 70     }
 71     N = cities.size();
 72 
 73     vector<vector<int> > memo(N, vector<int>(N));
 74     for (int i = 0; i < N; i++) {
 75       for (int j = 0; j < N; j++) {
 76         if (i == j) {
 77           continue;
 78         }
 79         const pair<bool,int> r = cities[j].search(cities[i].pat);
 80         memo[i][j] = cities[j].pat.size() - r.second;
 81       }
 82     }
 83 
 84     static const int INF = 10000000;
 85     vector<vector<int> > dp(1<<N, vector<int>(N, INF));
 86     for (int i = 0; i < N; i++) {
 87       dp[1<<i][i] = cities[i].pat.size();
 88     }
 89     for (unsigned s = 1; s < (1<<N); s++) {
 90       for (int i = 0; i < N; i++) {
 91         if (!(s & (1<<i))) {
 92           continue;
 93         }
 94         for (int j = 0; j < N; j++) {
 95           if (s & (1<<j)) {
 96             continue;
 97           }
 98           int& dp_next = dp[s|(1<<j)][j];
 99           dp_next = min(dp_next, dp[s][i] + memo[i][j]);
100         }
101       }
102     }
103     int ans = INF;
104     for (int i = 0; i < N; i++) {
105       ans = min(ans, dp[(1<<N)-1][i]);
106     }
107     cout << ans << endl;
108   }
109   return 0;
110 }
aoj/1320.cc