单词接龙

题目描述

$n$ （ $n\le 20$ ）个单词接龙，首词须以给定字母开头，相邻两词须有重叠且只计一次（beast+astonish→beastonish），不能整词包含（at 不能接 atide），每词最多用两次，求最长龙的长度。

输入第一行 $n$ ，随后 $n$ 行单词，最后一行为首字母。样例：5, at, touch, cheat, choose, tact, a → 输出 23。

思路

后续能接多长只取决于最后一个词和各词已用次数，与前面路径无关。先预处理每对单词的最小合法重叠（ $k<\min(|a|,|b|)$ 自动排除整词包含），再以「最后词 + 各词用量」为状态记忆化搜索，枚举接得上且未用满两次的后继取最大。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 04:27
# update_at: 2026-10-02 04:27

import sys
from functools import cache


def min_overlap(a: str, b: str) -> int | None:
    """a 后接 b 的最小合法重叠长度：k 从 1 试起，接不上返回 None。

    k 只试到 min(len(a), len(b)) - 1，自动排除整词包含——如 at 接 atide
    唯一能对上的重叠 k=2 恰好等于 len(at)，所以两词不能相连。
    """
    for k in range(1, min(len(a), len(b))):
        if a[-k:] == b[:k]:
            return k
    return None


def solve() -> None:
    data = iter(sys.stdin.read().split())
    word_count = int(next(data))
    words = [next(data) for _ in range(word_count)]
    head = next(data)

    # overlap[i][j]：词 j 接在词 i 后的最小合法重叠；None 表示接不上
    overlap: list[list[int | None]] = [
        [min_overlap(a, b) for b in words] for a in words  # n^2 对
    ]

    @cache
    def remain(last: int, used: tuple[int, ...]) -> int:
        """词 last 收尾、各词已用次数为 used 时，还能追加的最大字符数。"""
        best = 0
        for j, k in enumerate(overlap[last]):
            if used[j] == 2 or k is None:
                continue                                       # 用满两次或接不上
            used_j = used[:j] + (used[j] + 1,) + used[j + 1:]  # 只改第 j 位，保持 tuple 可哈希
            gain = len(words[j]) - k                           # 重叠部分在龙里只计一次
            best = max(best, gain + remain(j, used_j))
        return best

    # 龙头：任一以 head 开头的词做第一个词，整词计入长度
    ans = 0
    for i, w in enumerate(words):
        if w[0] != head:
            continue
        used = [0] * word_count
        used[i] = 1
        ans = max(ans, len(w) + remain(i, tuple(used)))
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 12:09
 * update_at: 2026-10-06 12:09
 */
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
using namespace std;

typedef long long ll;

const int MAXN = 25;

int n;                  // 单词数
string word[MAXN];      // word[i]：第 i 个单词（下标从 0 开始）
int len[MAXN];          // len[i]：第 i 个单词的长度
char head_char;         // 龙开头的字母
int overlap[MAXN][MAXN]; // overlap[i][j]：词 j 接在词 i 后的最小合法重叠长度，-1 表示接不上
ll pow3[MAXN];          // pow3[i] = 3^i，用来把各词用量编码进一个整数
map<ll, ll> memo;       // memo[last * pow3[n] + code]：还能追加的最大字符数

// 计算 a 后接 b 的最小合法重叠长度；k 只试到 min(len)-1，自动排除整词包含
int min_overlap(const string &a, int len_a, const string &b, int len_b) {
    int lim = min(len_a, len_b);
    for (int k = 1; k < lim; k++) {
        if (a.compare(len_a - k, k, b, 0, k) == 0) {
            return k; // 找到最小可行重叠，重叠部分在龙里只计一次
        }
    }
    return -1; // 不允许零重叠直接拼接
}

// 词 last 收尾、各词已用次数由 code 的三进制位表示时，还能追加的最大字符数
ll dfs(int last, ll code) {
    ll key = last * pow3[n] + code;
    map<ll, ll>::iterator it = memo.find(key);
    if (it != memo.end()) {
        return it->second; // 相同状态只算一次
    }

    ll best = 0;
    for (int j = 0; j < n; j++) {
        if (overlap[last][j] < 0) {
            continue; // 这两词接不上
        }
        ll digit = (code / pow3[j]) % 3;
        if (digit == 2) {
            continue; // 每个单词最多出现两次
        }
        ll next_code = code + pow3[j]; // 第 j 个词多用一个
        ll gain = len[j] - overlap[last][j];
        best = max(best, gain + dfs(j, next_code));
    }

    memo[key] = best;
    return best;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> word[i];
        len[i] = word[i].size();
    }
    cin >> head_char;

    pow3[0] = 1;
    for (int i = 1; i <= n; i++) {
        pow3[i] = pow3[i - 1] * 3;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            overlap[i][j] = min_overlap(word[i], len[i], word[j], len[j]);
        }
    }

    // 龙头：任一以 head_char 开头的词做第一个词，整词长度都计入
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (word[i][0] != head_char) {
            continue;
        }
        ll code = pow3[i]; // 第 i 个词用了一次
        ans = max(ans, len[i] + dfs(i, code));
    }

    cout << ans << endl;
    return 0;
}

目录

题目描述

思路

参考代码