[NOIP2000 提高组] 单词接龙
2025年2月26日小于 1 分钟
#include <bits/stdc++.h>
using namespace std;
int n;
string s[25];
char c;
int lnk[25][25];
int ans;
int cnt[25];
void dfs(int now, int len)
{
ans = max(ans, len);
for (int i = 1; i <= n; i++)
{
//cout << now << " " << i << " " << cnt[i] << " " << lnk[now][i] << endl;
if (cnt[i] < 2 && lnk[now][i])
{
cnt[i]++;
//cout << s[now] << "~" << s[i] << endl;
dfs(i, len + s[i].length() - lnk[now][i]);
cnt[i]--;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> s[i];
cin >> c;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
lnk[i][j] = 0;
for (int k = s[i].length() - 1; k > 0; k--)
{
bool flag = true;
for (int p = k; p <= s[i].length() - 1; p++)
if (s[i][p] != s[j][p - k])
{
flag = false;
break;
}
if (flag)
{
lnk[i][j] = s[i].length() - 1 - k + 1;
break;
}
}
}
}
ans = 0;
for (int i = 1; i <= n; i++)
if (s[i][0] == c)
{
cnt[i]++;
dfs(i, s[i].length());
cnt[i]--;
}
cout << ans << endl;
return 0;
}