AcWing 1117. 单词接龙
原题链接
简单
作者:
十六
,
2021-01-18 16:10:42
,
所有人可见
,
阅读 346
#include<bits/stdc++.h>
using namespace std;
const int MAX = 20+5;
int n, ans;
string w[MAX];
int g[MAX][MAX];
int cnt[MAX];
void getg(){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
for(int k=1; k<(int)min(w[i].size(), w[j].size()); k++){
//若要接龙最长,找最小的公共序列即可
if(w[i].substr(w[i].size()-k)==w[j].substr(0, k)){
g[i][j] = k;
break;
}
}
}
}
}
void dfs(int len, int per){
ans = max(len, ans);
for(int i=0; i<n; i++){
if(cnt[i]<2){
//有公共序列
if(g[per][i]){
cnt[i]++;
dfs(len+w[i].size()-g[per][i], i);
cnt[i]--;
}
}
}
}
int main(){
scanf("%d", &n);
for(int i=0; i<n; i++) cin>> w[i];
char c;
cin>> c;
getg();
ans = 0;
for(int i=0; i<n; i++){
if(w[i][0] == c){
cnt[i]++;
dfs(w[i].size(), i);
cnt[i]--;
}
}
cout<< ans<< endl;
return 0;
}