单词接龙

题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如

输入格式

输入的第一行为一个单独的整数

输出格式

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

输入输出样例

输入 #1

5
at
touch
cheat
choose
tact
a

说明/提示

（连成的“龙”为atoucheatactactouchoose）

NOIp2000提高组第三题

分析：

由于本题中n<=20，故可以尝试使用dfs暴力枚举下一个选择的字符串，并与上一个进行比对，这样的话是2^20，依然不会超时。

CODE:

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 const int M=105;
 8 int n;
 9 char s[M][M],c;
10 int get(){
11     int res=0,f=1;
12     char c=getchar();
13     while (c>'9'||c<'0') {
14         if (c=='-') f=-1;
15         c=getchar();
16     }
17     while (c<='9'&&c>='0'){
18         res=(res<<3)+(res<<1)+c-'0';
19         c=getchar();
20     }
21     return res*f;
22 }
23 int flag[M];
24 int ans;
25 void dfs(int last,int len){
26     //cout<<last<<" "<<len<<endl;
27     ans=max(ans,len);
28     for (int i=1;i<=n;i++){
29         //cout<<"guocheng"<<i<<" "<<last<<endl;
30         //cout<<s[i][1]<<" "<<s[last][strlen(s[last]+1)]<<" "<<flag[i]<<endl;
31         bool ok=false;
32         int pos=0;
33         int minn=1<<10;
34         for (int j=1;j<=min(strlen(s[last]+1),strlen(s[i]+1));j++){
35             bool bjj=true;
36             int x=strlen(s[last]+1);
37             for (int k=x;k>=x-j+1;k--){
38                 /*cout<<x<<" "<<j<<" "<<k<<" "<<j-(x-k)<<endl;
39                 cout<<s[i][j-(x-k)]<<" "<<s[last][k]<<endl;*/
40                 if (s[i][j-(x-k)]!=s[last][k]) {bjj=false;break;}
41             }
42             //cout<<j<<" "<<bjj<<" "<<pos<<endl;
43             if (bjj) ok=true,pos=j,minn=min(minn,pos);
44         }
45         //cout<<ok<<" "<<pos<<endl;
46         if (ok&&flag[i]<2&&((i==last&&pos!=minn)||pos!=strlen(s[i]+1))){
47             flag[i]++;
48             pos=min(pos,minn);
49             dfs(i,strlen(s[i]+1)+len-pos);
50             flag[i]--;
51         }
52     }
53     return ;
54 }
55 int main(){
56     n=get();
57     for (int i=1;i<=n;i++) scanf ("%s",s[i]+1);
58     scanf("
");
59     scanf ("%c",&c);
60     for (int i=1;i<=n;i++){
61         if (s[i][1]==c){
62             memset(flag,0,sizeof(flag));
63             flag[i]=1;
64             dfs(i,strlen(s[i]+1));
65         }
66     }
67     printf ("%d",ans);
68     return 0;
69 }