AcWing 1117. 单词接龙
原题链接
简单
作者:
哈基咪
,
2020-09-14 08:53:37
,
所有人可见
,
阅读 553
//单词接龙
// 1.单词接龙游戏中,想要使得龙的长度最长,那么两单词的重合部分就要取最小值
// 枚举顺序大致为,选择一个字符串拼接到后面,然后更新长度,再枚举下一个字符串,直到全部连接完成
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=21;
int st[N],n;//st为判重数组,每个字符串最多用两次
int new_dragon,max_dragon;//表示单词龙的长度
string str[N];
int matching(string &s1, string &s2)
{
//用来得到接龙时两单词的重合长度,s2是被拼接的
if(s1.length()==1)
{
if(s1[0]==s2[0])
{
//s1长度为1,且s1 s2第一个字符相等的话,那龙增加的长度就是s2-1
return s2.length();
}
else return 0;//拼接失败~
}
else
{
//说明两字符串长度都大于一,那么就少最短的重合长度
for(int i=1;i<s1.length();i++)
{
if(s1.substr(s1.length()-i,s1.length())==s2.substr(0,i))
{
return s2.length()-i;
}
}
}
}
void dfs(string &s)
{
//s为每次接龙完单词末尾的这一个单词
for(int i=0;i<n;i++)
{
//matching返回0的话说明匹配不成功
int t=matching(s,str[i]);
if(st[i]<2&&t)
{
new_dragon+=t;
if(new_dragon>max_dragon)
{
max_dragon=new_dragon;
}
st[i]++;
dfs(str[i]);
st[i]--;
new_dragon-=t;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
cin>>str[i];
}
string cr;
cin>>cr;
dfs(cr);
cout<<max_dragon<<endl;
return 0;
}