aoj1320:City Merger

問題文

City Merger | Aizu Online Judge

解法

dp[i][j]:=bit列iであらわされる集合に含まれるやつらを使って、末尾に文字列jがあるときの最小の長さ、とする。
あとは適当に

コード

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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N;
string S[14];

int dp[1<<14][14];

int table[14][14];

signed main(){
    while(cin>>N,N){
        rep(i,N)cin>>S[i];
        memset(table,0,sizeof(table));
        fill_n(*dp,(1<<14)*14,1001001001);
        rep(i,N)dp[1<<i][i]=S[i].size();

        rep(i,N){
            rep(j,N){
                if(S[i].find(S[j])!=string::npos)table[i][j]=-1;
                else{
                    for(int k=1;k<=(int)min(S[i].size(),S[j].size());k++){
                        if(S[i].substr(S[i].size()-k,k)==S[j].substr(0,k))table[i][j]=k;
                    }
                }
            }
        }

        reps(i,1,1<<N){
            rep(j,N)if(i>>j&1){
                rep(k,N)if(!(i>>k&1)){
                    if(table[j][k]==-1)chmin(dp[i|(1<<k)][j],dp[i][j]);
                    else chmin(dp[i|(1<<k)][k],dp[i][j]+S[k].size()-table[j][k]);
                }
            }
        }

        int mi=1001001001;
        rep(i,N)chmin(mi,dp[(1<<N)-1][i]);
        cout<<mi<<endl;
    }
    return 0;
}