AOJ - RESTORE 실험 데이터 복구하기

AOJ - RESTORE

전처리해야 할 과정이 좀 있어서 귀찮다.

우리가 $dp[bit][last]$ 를 마지막에 $last$ 를 썼고, 지금 사용할 수 있는 단어를 이진수 $bit$ 로 가지고 있는다고 해보자.

$dp$ 값은 모두 사용했을 때 최소 길이를 의미한다.

문제가 되는 경우는 마지막이 $abc$ 인데 지금 붙이는게 $aaabc$ 같은 것처럼 포함이 되는 경우이다.

마지막이 $abc$ 라는 정보를 이용해 지금까지 붙인 문자열중 마지막 3글자가 $abc$ 라는 점을 알 수 있는데, 그 전에는 정보를 알 수 없기 때문이다.

생각해보면 $aaabc$ 가 있다면 $abc$ 는 없어도 되기 때문에 $S_i$ 가 $S_j$에 포함된다면 $S_i$ 를 아예 제외해주고 풀어줄 수 있다.

그리고 $S_i$의 suffix가 $S_j$의 prefix와 얼마나 겹치는지를 미리 전처리해서 $O(1)$에 가져올 수 있게 준비해주면 된다.

마지막으로 가장 첫 문자열은 더미 단어를 하나 붙여놓음으로써 구현에 편의를 얻을 수 있다.

void solve() {  
   int n;  
   cin >> n;  
   vs a(n);  
   fv(a);  
   vi included(n);  
   for (int i = 0; i < n; i++) {  
      for (int j = 0; j < n; j++) {  
         if (i ^ j && hasstr(a[i], a[j]) && a[i] != a[j]) {  
            included[j] = 1;  
         }  
      }  
   }  
   vs b;  
   for (int i = 0; i < n; i++) if (!included[i]) b.pb(a[i]);  
   n = sz(b);  
   assert(n);  
   a = b;  
   a.insert(a.begin(), "^");  
   n++;  
  
   vvi dup(n, vi(n));  
   for (int i = 0; i < n; i++) {  
      for (int j = 0; j < n; j++) {  
         if (i ^ j) {  
            for (int k = 1; k <= min(sz(a[i]), sz(a[j])); k++) {  
               if (a[i].substr(sz(a[i]) - 1 - k + 1, k) == a[j].substr(0, k))  
                  dup[i][j] = k;  
            }  
         }  
      }  
   }  
  
   vvi dp(1 << (n + 1), vi(n, -1));  
   function<int(int, int)> fn = [&](int bit, int last) -> int {  
      int cnt = __builtin_popcount(bit);  
      if (cnt == 0) return 0;  
      int &ret = dp[bit][last];  
      if (~ret) return ret;  
      ret = 1e9;  
  
      for (int i = 0; i < n; i++) {  
         if (bit & (1 << i)) {  
            ret = min(ret, fn(bit & ~(1 << i), i) + sz(a[i]) - dup[last][i]);  
         }  
      }  
  
      return ret;  
   };  
   string ans;  
   function<void(int, int)> trace = [&](int bit, int last) -> void {  
      int cnt = __builtin_popcount(bit);  
      if (cnt == 0) return;  
      for (int i = 0; i < n; i++) {  
         if (bit & (1 << i)) {  
            if (fn(bit, last) == sz(a[i]) - dup[last][i] + fn(bit & ~(1 << i), i)) {  
               ans += a[i].substr(dup[last][i]);  
               trace(bit & ~(1 << i), i);  
               return;  
            }  
         }  
      }  
   };  
   int start = ((1 << n) - 1) ^ 1;  
   trace(start, 0);  
   cout << ans << endl;  
}