题目背景
注意:本题为上古 NOIP 原题,不保证存在靠谱的做法能通过该数据范围下的所有数据。
题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beast
和 astonish
,如果接成一条龙则变为 beastonish
,另外相邻的两部分不能存在包含关系,例如 at
和 atide
间不能相连。
输入格式
输入的第一行为一个单独的整数 n 表示单词数,以下 n 行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。
输出格式
只需输出以此字母开头的最长的“龙”的长度。
输入输出样例
输入 #15 at touch cheat choose tact a输出 #1
23
说明/提示
样例解释:连成的“龙”为 atoucheatactactouchoose
。
≤20n≤20。2023-06-07
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e5+10; 4 int n,res,vis[N]; 5 string s[30],st; 6 int chong(string s1,string s2) 7 { 8 for(int i=s1.size()-1;i>=0;i--) 9 { 10 if(s1[i]==s2[0]) 11 { 12 int l=i; 13 for(int j=0;j<s2.size();j++) {if(s1[l]==s2[j]) l++;else break;} 14 if(l==s1.size()) return l-i; 15 } 16 } 17 return 0; 18 } 19 void dfs(int num,string now) 20 { 21 res=max(res,(int)now.size()-num); 22 for(int i=0;i<n;i++) 23 { 24 int p=0; 25 if(vis[i]>=2) continue; 26 p=chong(now,s[i]); 27 if(p==0) continue; 28 vis[i]++; 29 dfs(num+p,now+s[i]); 30 vis[i]--; 31 } 32 } 33 int main() 34 { 35 cin>>n; 36 for(int i=0;i<n;i++) cin>>s[i]; 37 cin>>st; 38 dfs(0,st); 39 cout<<res; 40 return 0; 41 }
标签:NOIP2000,string,int,字母,单词,接龙,开头 From: https://www.cnblogs.com/o-Sakurajimamai-o/p/17463153.html