AOJ 1320 City Merger

問題文(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1320)

AOJ2022(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2022)とほとんど同じ問題。他の都市名の部分文字列になっている都市名を予め取り除いてからbitDPをする。

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

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;

const int INF = 1e9;
const ld EPS = 1e-8;

bool is_contained(string s, string t) {
  for(int i = 0; i + s.length() - 1 < t.length(); ++i) {
    if(s == t.substr(i, s.length())) return true;
  }
  return false;
}

int d[16][16];
int memo[16][1<<16];

int dp(int n, int k, int S) {
  //cout << k << " " << S << endl;
  if(memo[k][S] != INF) return memo[k][S];
  if(S == (1<<k)) return d[k][k];
  int res = INF;
  REP(i, n){
    if(i == k) continue;
    if(S & (1<<i)){
      res = min(res, d[k][i] + dp(n, i, S - (1<<k)));
    }
  }
  //cout << k << " " << S << ": " << res << endl;
  return memo[k][S] = res;
}

int main(){
  int n;
  while(cin >> n && n) {
    vector<string> cities(n);
    REP(i,n) cin >> cities[i];
    vector<string> tmp;
    REP(i,n){
      bool flag = true;
      REP(j,n){
        if(i == j) continue;
        if(is_contained(cities[i], cities[j])){
          flag = false;
          break;
        }
      }
      if(flag) tmp.push_back(cities[i]);
    }
    cities = tmp;
    n = cities.size();

    REP(i,16)REP(j,16) d[i][j] = INF;
    REP(i,n)REP(j,n){
      string s = cities[i];
      string t = cities[j];
      bool flag = true;
      for(int k = max(0, (int)(s.length() - t.length())); k < s.length(); ++k){
        if(s.substr(k) == t.substr(0, s.length() - k)){
          d[i][j] = k;
          flag = false;
          break;
        }
      }
      if(flag) d[i][j] = s.length();
    }
    REP(i,n) d[i][i] = cities[i].length();
    
    int res = INF;
    REP(i,16)REP(j,1<<16) memo[i][j] = INF;
    REP(i,n){
      int tmp = dp(n, i, (1<<n) - 1);
      res = min(res, tmp);
    }
    cout << res << endl;
  }
  return 0;
}