P1019 单词接龙 题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。
输入输出格式
输入格式： 输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出格式： 只需输出以此字母开头的最长的“龙”的长度
输入输出样例
输入样例#1： 5 at touch cheat choose tact a 输出样例#1： 23 （连成的“龙”为atoucheatactactouchoose） 说明
NOIp2000提高组第三题
这是一道dfs+字符串
接龙的规则是前后字符串有相同的部分（一开始以为是单个字符）。
而且每个串只能用两次。
因为只有二十个串，所以可以直接用搜索
再说字符串的连接的判断。
先取后一个字符串的第一个字符，在前者由后往前找一个相同的字符。然后两个指针分别判断由此到最后一个字符是否全部相同。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
int vis[
21];
int n;
char dragon[
21][
256];
int len[
21];
int maxs =
0;
inline int read(){
char c;
int res,flag =
0;
while((c = getchar())>
'9'||c<
'0')
if(c==
'-')flag =
1;
res = c -
'0';
while((c = getchar())>=
'0'&&c<=
'9')
res =(res<<
3)+(res<<
1) + c -
'0';
return flag?-res:res;
}
inline int check(
int a,
int b){
int i,k,j;
for(i=len[a]-
1;i>=
1;i--){
if(dragon[a][i]==dragon[b][
0]){
int x=
0;
for(k=i,j=
0;k<len[a]&&j<len[b];k++,j++){
if(dragon[a][k]==dragon[b][j])x++;
else break;
}
if(k==len[a])
return x;
}
}
return 0;
}
void dfs(
int i,
int lenx){
bool flag =
true;
for (
int j =
1;j<=n;j++){
if(vis[j] <
2){
int t = check(i,j);
if(t!=
0){
flag =
false;
vis[j]++;
dfs(j,lenx+len[j]-t);
vis[j]--;
}
}
}
if(flag ==
true){
maxs = max(maxs,lenx);
}
}
int main(){
n = read();
for (
int i =
1;i<=n;i++){
cin>>dragon[i];
len[i] =
strlen(dragon[i]);
}
char c;
cin>>c;
memset(vis,
0,
sizeof(vis));
for (
int i =
1;i<=n;i++){
if(dragon[i][
0] == c){
vis[i]+=
1;
dfs(i,len[i]);
memset(vis,
0,
sizeof(vis));
}
}
cout<<maxs;
}
