AOJ 1320 City Merger

有點麻煩的題目，算出overlap，然後再計算有沒有子字串在裡面，子字串可以直接不用考慮

那麼把剩餘的點拿來做Hamilton Path最小成本即可

/*
 * GCA : "Computer is artificial subject absolutely,Math is God"
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
#include <ctime>
using namespace std;
#ifdef DEBUG
#define VAR(a,b) __typeof(b) a=(b)
#define debug(...) printf("DEBUG: "),printf(__VA_ARGS__)
#else
#define VAR(a,b) __typeof(b) a=(b)
#define debug(...)
#endif
typedef unsigned int uint;
typedef long long int Int;
typedef unsigned long long int UInt;
#define Set(a,s) memset(a,s,sizeof(a))
#define Pln() printf("\n")
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define M 25
#define PB push_back
#define oo INT_MAX
#define FOR(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)
#define eps 1e-9
#define X first
#define Y second
inline bool xdy(double x,double y){return x>y+eps;}
inline bool xddy(double x,double y){return x>y-eps;}
inline bool xcy(double x,double y){return x<y-eps;}
inline bool xcdy(double x,double y){return x<y+eps;}
const Int mod=1000000007;
int n;
char str[M][M];
int mz[M][M];
int pnt[M];
bool nonused[M];
bool substr(int x,int y){
    int xlen=strlen(str[x]);
    int ylen=strlen(str[y]);
    string sx(str[x]),sy(str[y]);
    if(ylen>xlen)return false;
    for(int i=0;i<=xlen-ylen;i++){
        if(sx.substr(i,ylen)==sy)return true;
    }
    return false;
}
int count_w(int x,int y){
    int len=strlen(str[x]);
    int len2=strlen(str[y]);
    for(int i=max(0,len-len2);str[x][i];i++){
        bool suc=true;
        int j,k;
        for(j=i,k=0;str[x][j]&&str[y][k];j++,k++){
            if(str[x][j]!=str[y][k]){
                suc=false;
                break;
            }
        }
        if(suc)return k;
    }
    return 0;
}
int dp[1<<15][15];
int dfs(int s,int now,int dep){
//    debug("%d %d\n",now,dep);
    if(s==(1<<n)-1){
        return 0;
    }
    if(dp[s][now]!=-1)return dp[s][now];
    int minans=-1,t;
    for(int i=0;i<n;i++){
        if(i!=now&&!((s>>i)&1)){
            int h;
            if((h=dfs(s|(1<<i),i,dep+1))!=-1){
                t=h+strlen(str[pnt[i]])-mz[now][i];
            }
            if(minans==-1||t<minans){
                minans=t;
            }
        }
    }
    return dp[s][now]=minans;
}
void solve(){
    Set(nonused,0);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)continue;
            if(substr(i,j))nonused[j]=1;
        }
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        if(!nonused[i])pnt[cnt++]=i;
    }
    n=cnt;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)continue;
            mz[i][j]=count_w(pnt[i],pnt[j]);
//            debug("%d %d %d\n",i,j,mz[i][j]);
        }
    }
    Set(dp,-1);
    int ans=oo;
//    ans=dfs(1,0,0);
    for(int i=0;i<n;i++){
        int t=strlen(str[pnt[i]])+dfs(1<<i,i,0);
        ans=min(ans,t);

    }
    printf("%d\n",ans);
}
int main() {
    ios_base::sync_with_stdio(0);
    while(~scanf("%d",&n)&&n){
        for(int i=0;i<n;i++)scanf("%s",str[i]);
        Set(mz,0);
        solve();
    }

















}