本題求用最短的長度字符串包含所給子串...由於存在多串匹配的問題...容易聯想到AC自動機...
最多14個city..用14位的二進制數表示已經在串中否...對多串構造Trie樹..進一步構造好AC自動機...可以用dp [ k ] [ i ] [ x ] 來表示長度為k的串..末字符落在trie樹的i處..包含14個關系的x...但這樣的復雜度..以最壞的考慮..會有240*240*16384=943718400=9*10^8...無法接受...
那麼此時就要壓縮路徑了..由於Trie樹中有很多無法產生更新的點...沒必要dp時一次又一次的路過...所以將Trie樹中x非0的點找出來...從每個點開始BFS...做出到其他有效點的最短距離...這樣大大優化了dp過程...
Program:
[cpp]
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<stack>
#include<math.h>
#include<map>
#define oo 1000000000
using namespace std;
struct node
{
int fail,son[26],city,w;
}point[1001];
struct node2
{
int len,x;
};
int n,m,k,g,arc[303][303],need[303],l[303],dp[2][303][18000];
char s[30];
queue<int> myqueue;
void Built_Trie()
{
int len,i,j,k,h,x;
memset(point,0,sizeof(point));
m=0; g=1;
for (k=0;k<n;k++)
{
scanf("%s",s);
len=strlen(s);
h=0;
for (i=0;i<len;i++)
{
x=s[i]-'A';
if (!point[h].son[x]) point[h].son[x]=++m;
h=point[h].son[x];
}
point[h].w|=g;
g*=2;
}
g--;
return;
}
void Built_AC_Automation()
{
int i,h,k;
while (!myqueue.empty()) myqueue.pop();
for (i=0;i<26;i++)
if (point[0].son[i]) myqueue.push(point[0].son[i]);
while (!myqueue.empty())
{
h=myqueue.front();
myqueue.pop();
point[h].w|=point[point[h].fail].w;
for (i=0;i<26;i++)
{
k=point[h].fail;
while (!point[k].son[i] && k) k=point[k].fail;
point[point[h].son[i]].fail=point[k].son[i];
if (!point[h].son[i])
point[h].son[i]=point[k].son[i];
else
myqueue.push(point[h].son[i]);
}
}
return;
}
void Built_Arc()
{
int i,k,h,len[303];
memset(arc,-1,sizeof(arc));
n=0;
for (k=0;k<=m;k++)
if (point[k].w)
{
need[n++]=k;
point[k].city=n;
}
need[n]=0;
for (k=0;k<=n;k++)
{
h=need[k];
memset(len,-1,sizeof(len));
myqueue.push(h);
len[h]=0;
while (!myqueue.empty())
{
h=myqueue.front();
myqueue.pop();
i=h;
do
{
if (point[h].w && arc[k][point[h].city-1]==-1)
arc[k][point[h].city-1]=len[h];
i=point[i].fail;
}while (i);
for (i=0;i<26;i++)
if (len[point[h].son[i]]==-1)
{
len[point[h].son[i]]=len[h]+1;
myqueue.push(point[h].son[i]);
}
}
}
for (i=0;i<n;i++) l[i]=arc[n][i];
return ;
}
int EXE_DP()
{
int p,i,j,t,k,x,ans;
memset(dp,-1,sizeof(dp));
k=0;
for (i=0;i<n;i++) dp[k][i][point[need[i]].w]=l[i];
for (t=1;t<=n;t++)
{
k=1-k;
memset(dp[k],-1,sizeof(dp[k]));
for (i=0;i<n;i++)
for (j=0;j<n;j++)
for (p=0;p<=g;p++)
if (dp[1-k][j][p]!=-1)
{
x=point[need[i]].w|p;
if (dp[k][i][x]==-1 || dp[k][i][x]>dp[1-k][j][p]+arc[j][i])
dp[k][i][x]=dp[1-k][j][p]+arc[j][i];
}
}
ans=oo;
for (i=0;i<n;i++)
if (dp[k][i][g]!=-1 && dp[k][i][g]<ans) ans=dp[k][i][g];
return ans;
}
int main()
{
while (~scanf("%d",&n))
{
if (!n) break;
Built_Trie();
Built_AC_Automation();
Built_Arc();
printf("%d\n",EXE_DP());
}
return 0;
}
