8783:单词接龙

总时间限制: 1000ms 内存限制: 65536kB

描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。

输入

输入的第一行为一个单独的整数n(n<=20)表示单词数，以下n行每行有一个单词（只含有大写或小写字母，长度不超过20），输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

输出

只需输出以此字母开头的最长的“龙”的长度。

样例输入

5 at touch cheat choose tact a

样例输出

23

提示

连成的“龙”为atoucheatactactouchoose

来源

NOIP2000复赛 普及组 第四题

【思路+代码】

#include<cstdio> #include<string> #include<iostream> #include<algorithm> using namespace std; string a[21]; int n,maxn,used[21],l=1; void dfs(int c)//a[c]已定单词，a[i]接龙单词 { int lc,li; maxn=max(maxn,l); for(int i=1;i<=n;i++) if(used[i]<2) { for(int j=0;j<a[c].length();j++)//将已定单词的每一个字母逐一与接龙单词 if(a[c][j]==a[i][0])//的首字母比较，从相同的地方开始接 { lc=j; li=0;//记录接龙起点 while(a[c][lc]==a[i][li]&&lc<a[c].length())//逐个比对，如果相同且长度没超过已定单词的长度就累加长度 { lc++; li++; } if(lc==a[c].length())//如果比对到了，就接上长度（到达目标） { l+=a[i].length()-li; used[i]++; dfs(i); l-=a[i].length()-li; used[i]--; } } } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) cin>>a[i]; cin>>a[n+1]; dfs(n+1);//把头字母也当成一个单词，从头字母开始搜 printf("%d",maxn); }