AcWing 1117. 单词接龙
原题链接
简单
作者:
无缘铜行者
,
2021-03-18 19:26:27
,
所有人可见
,
阅读 272
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
string a[40];
int vis[40];
int n;
//找到前面的单词和后面的单词能重合多少个字符
//没有重合则返回-1
int get(int i1, int i2){
int len1 = a[i1].size(), len2 = a[i2].size();
int len = min(len1, len2);
for(int i = 1; i < len; ++i){
for(int j = 0; j < i; ++j){
if(a[i1][len1 - i + j] != a[i2][j]) break;
if(j == i - 1) return i;
}
}
return -1;
}
int dfs(int idx){
int ans = 0;
for(int i = 0; i < 2 * n; ++i){
if(vis[i]) continue;
int d = get(idx, i);
if(d == -1) continue;
vis[i] = 1;
ans = max(ans, int(a[i].size()) - d + dfs(i));
vis[i] = 0;
}
return ans;
}
int main(){
cin >> n;
for(int i = 0; i < n; ++i){
cin >> a[i];
a[i + n] = a[i];
}
string s;
cin >> s;
char s0 = s[0];
int ans = 0;
for(int i = 0; i < n; ++i){
if(a[i][0] == s0){
vis[i] = 1;
ans = max(ans, int(a[i].size()) + dfs(i));
vis[i] = 0;
}
}
return 0;
}