AOJ 1320 : City Merger

問題リンク：City Merger | Aizu Online Judge

解法：
巡回セールスマン問題みたいであった

cost[i][j] := 文字列jを文字列iの後ろにつなげてできる文字列の長さから文字列iの長さを引いた値

dp[1<

for i 0..n // 初期化 これ以外はinf 
  dp[1<<i][i] = s[i].length() //s[i] は 文字列i

for S i 0..(1<<n)-1
  for from 0..n //状態Sでfromからtoへ行く
    if !((S>>from) & 1) //まだfromを訪れていない
      continue
    for to 0..n
      if (S>>to) & 1 // もう既にtoは訪れた
        continue
      dp[S|(1<<to)][to] = min(dp[S|(1<<to)][to],
                              dp[S][from] + cost[from][to]

最終的な答えはdp[(1<

#include<iostream>
#include<vector>
#include<cassert>
#include<algorithm>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define MAX 16
using namespace std;
 
int n;
int cost[MAX][MAX];
string s[MAX];
int dp[1<<MAX][MAX];
 
int getCost(string a,string b)
{//from a to b
  int res = inf;
  for(int i=a.size()-1,st = 0;i>=0 && st < b.size();i--,st++)
    {
      string ca = a.substr(i,a.size()-i);      
      string cb = b.substr(0,st+1);
      if(ca == cb)res = st+1; 
    }
  return res;
}
 
int main()
{
  while(cin >> n,n)
    {
      rep(i,n)rep(j,n)cost[i][j] = inf;
      rep(i,n)cin >> s[i];
      vector<string> ss;
      rep(i,n)
    {
      bool contain = false;
      rep(j,n)
        {
          if(i == j)continue;
          if(s[j].find(s[i]) != string::npos)
        {
 
          contain = true;
          break;
        }
        }
      if(!contain)ss.push_back(s[i]);
    }
 
      n = ss.size();
      rep(i,n)
    {
      rep(j,n)
        {
          if(i == j)
        {
          cost[i][j] = ss[i].size();
          continue;
        }
          int ct = getCost(ss[i],ss[j]);
          if(ct == inf)cost[i][j] = ss[j].size();
          else cost[i][j] = ss[j].size() - ct;
        }
    }
      rep(i,1<<n)rep(j,n)dp[i][j] = inf;
      rep(i,n)dp[1<<i][i] = ss[i].length();
 
      rep(S,(1<<n))
    {
      rep(from,n)
        {
          if(!((S>>from) & 1))continue;
          rep(to,n)
        {
          if((S>>to) & 1)continue;
          dp[S|(1<<to)][to] = min(dp[S|(1<<to)][to],
                      dp[S][from] + cost[from][to]);
        }
        }
    }
      int ans = inf;
      rep(i,n)ans = min(ans,dp[(1<<n)-1][i]);
 
      cout << ans << endl;
    }
  return 0;
}