单词具体是什么不重要，知道单词间如何转化即可
【分析】
先理清一下题意：
- (n)个单词，每个单词限用两次
- 上一个单词能与下一个单词接上，当且仅当上一个单词的末尾 (k) 个字符与下一个单词开头的 (k) 个字符完全相同
- 给定开头，求最长字符串的长度
我们可以发现，如果我们知道每个单词上一个单词能接哪些单词、下一个单词能接哪些单词、单词的长度，我们接下来的问题都与单词没关系了
同时，假设有两个单词 (W_1) 与 (W_2)，长度分别为 (L_1,L_2) ，它们之间的公共部分的长度可以是 (a_1 , a_2 , a_3dots a_m(a_1<a_2<a_3<dots<a_m))
我们要使得总字符串最长，即需要令 (W_1) 与 (W_2) 的接龙最长
因为它们接龙的长度为 ((L_1+L_2-a_i),1leq ileq m)
所以我们一定要选择最小的 (a_1) ，这样才能保证接龙最长
用 (Len_i) 表示单词 (i) 的长度， (App_i) 表示单词 (i) 的出现次数
用 (Con_{i,j}) 表示单词 (i) 后接单词 (j) 时它们的最短公共长度
当然，当 (Con_{i,j}=0) 时表示单词 (i) 后接单词 (j) 的最短公共长度为 (0) ，即没有公共部分，那么当然 (i) 不能后接 (j)
我们可以用 string 类来储存各个单词，毕竟 string 作为“合法公民”，可以直接用 “==” 比较是否相同
设我们用 string 类 (s_i) 表示第 (i) 个单词
根据 string 的自带函数即可轻松完成 (Len_i,Con_{i,j}) 的统计：
//统计 Len[i]
for(register int i=1;i<=N;i++) Len[i]=s[i].size();
//统计 Con[i][j]
for(register int i=1,I=d_N;i<=I;i++)//枚举第一个单词
for(register int j=1,J=d_N;j<=J;j++)//枚举第二个单词
for(register int k=1,K=Min(ar_d_Len[i],ar_d_Len[j]),k<=K;k++)//枚举公共长度
if ( s[i].substr(ar_d_Len[i]-k,k)==s[j].substr(0,k) ){
mt_d_Con[i][j]=k;
break;
//第一次找到的公共长度一定最短
}
//s.substr(p,l) 表示截取 s ，从第 p 个变量开始的 l 个字符，的字串，返回值为一个 string 变量
开头怎么处理？
很简单，开头视为单词 (s_0)，照常处理， (App_0) 标记为 (1) ，代表只能用 (1) 次即可
最后，我们深搜的时候直接从 (s_0) 开始
每次根据当前第 (i) 个单词，枚举 (Con_{i,j} eq 0) 的单词 (j) ，长度增加 ((Len_j-Con_{i,j})) 即可
【代码】
那本蒟蒻就放 我码风极丑的 代码了
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
using namespace std;
#define f(a,b,c,d) for(register int a=b,c=d;a<=c;a++)
#define g(a,b,c,d) for(register int a=b,c=d;a>=c;a--)
typedef int i32;
typedef unsigned int u32;
typedef long long int i64;
typedef unsigned long long int u64;
inline i32 Min(i32 a,i32 b) { return (a<b)?a:b; }
inline i32 Max(i32 a,i32 b) { return (a>b)?a:b; }
i32 d_N,ar_d_App[32]={0},ar_d_Len[32]={0},mt_d_Con[32][32]={0};
inline bool alw(char c) { return (c!='
')&&(c!='
'); }
inline void getstring(string &s){
string t;
getline(cin,t);
if( !alw(t[ t.size()-1 ]) ) s=t.substr(0, t.size()-1 );
else s=t;
}
inline i32 input(){
scanf("%d
",&d_N);
string s[32];
f(i,1,I,d_N) getstring(s[i]);
getstring(s[0]);
f(i,0,I,d_N) ar_d_Len[i]=s[i].size();
//i->j
f(i,0,I,d_N)
f(j,1,J,d_N)
f(k,1,K,Min(ar_d_Len[i],ar_d_Len[j]))
if ( s[i].substr(ar_d_Len[i]-k,k)==s[j].substr(0,k) ){
mt_d_Con[i][j]=k;
break;
}
ar_d_App[0]=1;
return s[0].size();
}
i32 dfs(i32 d_P){
ar_d_App[d_P]++;
i32 d_Ans=0;
f(i,1,I,d_N) if(mt_d_Con[d_P][i]>0&&ar_d_App[i]<2){
i32 d_Tmp=dfs(i)+ar_d_Len[i]-mt_d_Con[d_P][i];
d_Ans=Max(d_Ans,d_Tmp);
}
ar_d_App[d_P]--;
return d_Ans;
}
int main(){
i32 d_Ans=input();
cout<<dfs(0)+d_Ans;
return 0;
}
最后安利一下 本蒟蒻的博客