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);  
}