题目描述
题目大致含义如下:
已知:一组单词(给定一个开头的字母)
求: 以这个字母开头的最长的“龙”
(注:每个单词最多只能用两次)
注意:1.在两个单词相连时,其重合部分合为一部分
(例如:beast+astonish-> beastonish)
2.重合部分的长度可以任意选择,但其长度必须大于 等于1且严格小于两个串的长度
(例如:at 和 atide 不能相连)
样例
·样例输入:
5
at
touch
cheat
choose
tact
a
·样例输出:
23
·样例解释:连成的“龙”为 atoucheatactactouchoose。
题目分析
数据范围n≤20,我们由此可以想到可以用搜索来解决
先预处理出每个单词与其他单词的最短的公共部分及其长度。接下来,枚举每一个单词,判断是否能与起始字母接龙,若当前单词能够与起始字母接龙,那么就以此单词开始接龙,向下进行dfs。
下面上代码,附带注释 ^-^
参考代码
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=30;
int n;
int ans;
string word[N];
int g[N][N];
int used[N];
void init(){ //预处理出每个单词与其他单词的是否有公共部分及其长度
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
string a=word[i],b=word[j];
for(int k=1;k<min(a.size(),b.size());k++){ //枚举单词的每一位
if(a.substr(a.size()-k,k)==b.substr(0,k)){ //若单词a的后k位与单词b的前k位相同
g[i][j]=k; //记录下此时最小的k
break; //并返回,枚举与下一个单词的公共部分
}
}
}
}
void dfs(string dragon,int last){ //dragon:当前单词的龙;last:上一个单词的编号
ans=max((int)dragon.size(),ans); //更新当前答案
used[last]++;
for(int i=1;i<=n;i++)
if(g[last][i]&&used[i]<2) //第i个单词与上一个单词有公共部分&&用过不超过2次
dfs(dragon+word[i].substr(g[last][i]),i);
used[last]--; //回溯
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>word[i];
char strat;
cin>>strat; //输入起始字母
init();
for(int i=1;i<=n;i++){ //枚举每一个单词,判断是否能与起始字母接龙
if(word[i][0]==strat){ //若当前单词能够与起始字母接龙
dfs(word[i],i); //从此单词开始接龙
}
}
cout<<ans;
return 0;
}
蒟蒻在线报道
大佬tql
%%% tql