自动搬运

查看原文

来自洛谷，原作者为

	RyanLi 跟着光，靠近光，成为光，散发光。

搬运于2025-08-24 21:19:59，当前版本为作者最后更新于2025-02-18 21:19:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门：P1019 [NOIP 2000 提高组] 单词接龙

更佳的阅读体验：洛谷 P1019 题解

题目没有给字符串的数据范围，但有 $n \le 20$，尝试搜索发现可以通过本题。

在搜索时处理重合部分为本题难点，需要留意截取字串的边界问题（即下文代码 dfs() 函数中的 $i$ 和 $j$）。

#include <iostream>
using namespace std;

const int N = 30;
int n, vis[N], ans;
string s[N];
char c;

void dfs(const string &tmp) {
    ans = max(ans, int(tmp.size()));
    for (int i = 1; i <= n; ++i) {
        if (vis[i] >= 2) continue;
        for (int j = 1; j < min(tmp.size(), s[i].size()); ++j)
            if (tmp.substr(tmp.size() - j) == s[i].substr(0, j)) {
                ++vis[i];
                dfs(tmp + s[i].substr(j));
                --vis[i];
            }
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> s[i];
    cin >> c;
    for (int i = 1; i <= n; ++i) if (s[i][0] == c) {
        ++vis[i];
        dfs(s[i]);
        --vis[i];
    } cout << ans << '\n';
    return 0;
}