与上题类似 预处理一下各字符串之间最大的相同字符数就可以 注意dp要初始为负无穷
#include <iostream>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define N 1050
int dp[N][],k[],q[][N],w[][],f[N];
char s[][];
int compare(int x,int y)
{
int i,j,maxz=;
for(i = ; i < k[x] ; i++)
for(j = ; j < k[y] ; j++)
{
if(s[x][i]==s[y][j])
{
int ii = i+,jj = j+,o=;
while(ii<k[x]&&jj<k[y])
{
if(s[x][ii]==s[y][jj])
o++;
ii++;jj++;
}
maxz = max(o,maxz);
}
}
return maxz;
}
int main()
{
int i,j,n,e,o;
while(scanf("%d%*c",&n)&&n)
{
int kk=;
memset(w,,sizeof(w));
memset(dp,,sizeof(dp));
memset(f,,sizeof(f));
for(i = ; i < n ; i++)
{
scanf("%s",s[i]);
k[i] = strlen(s[i]);
}
for(i = ; i < n ;i++)
{
q[][i] = <<i;
dp[<<i][i] = ;
}
kk = n;
for(i =; i < n ; i++)
for(j = i+; j < n ; j++)
{
w[i][j] = compare(i,j);
w[j][i] = w[i][j];
}
for(i = ; i < n ; i++)
{
int tt=;
for(j = ; j < kk ; j++)
{
for(e = ; e < n ; e++)
{
for(o = ; o < n ; o++)
{
if(((~q[(i-)%][j])&(<<o))==)
continue;
int oo = q[(i-)%][j]+(<<o);
if(o==e)
continue;
dp[oo][o] = max(dp[oo][o],dp[q[(i-)%][j]][e]+w[e][o]);
if(!f[oo])
{
q[i%][tt++] = oo;
f[oo] = ;
}
}
}
}
kk = tt;
}
int ans = ;
for(i = ; i < n ;i++)
ans = max(ans,dp[(<<n)-][i]);
printf("%d\n",ans);
}
return ;
}