【题解】
入门搜索题。
先n方枚举每对单词，计算他们接龙可以让长度延长多少，可以延长的在链式前向星中加边。
搜索的时候按照边表逐个扩展就好了。
【代码】
#include#include #include #define LL long long#define rg register#define N 1010using namespace std;int n,ans,tot,last[N],len[N],v[N];char a[N][N],st;struct edge{ int to,pre,del;}e[200010];inline int read(){ int k=0,f=1; char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); return k*f;}inline void calc(int x,int y){ int st=max(2,len[x]-len[y]+2),del=0; // printf("%d %d %d\n",x,y,st); for(rg int i=st;i<=len[x];i++){ bool ok=1; for(rg int j=1;j<=len[x]-i+1;j++)if(a[x][i+j-1]!=a[y][j]){ ok=0; break; } if(ok) del=len[y]-(len[x]-i+1); } if(del>0){ e[++tot]=(edge){y,last[x],del}; last[x]=tot; // printf("[%d %d del=%d]\n",x,y,del); }}void dfs(int now,int lenth){ ans=max(ans,lenth); for(rg int i=last[now],to;i;i=e[i].pre)if(v[to=e[i].to]<2){ v[to]++; dfs(to,lenth+e[i].del); v[to]--; }}int main(){ n=read(); for(rg int i=1;i<=n;i++){scanf("%s",a[i]+1); len[i]=strlen(a[i]+1);} st=getchar(); while((!('a'<=st&&st<='z'))&&(!('A'<=st&&st<='Z'))) st=getchar(); // for(rg int i=1;i<=n;i++) printf("[%s]\n",a[i]+1); for(rg int i=1;i<=n;i++) for(rg int j=1;j<=n;j++) calc(i,j); for(rg int i=1;i<=n;i++)if(a[i][1]==st){ v[i]++; dfs(i,len[i]); v[i]--; } printf("%d\n",ans); return 0;}