单词接龙

题目描述

单词接龙：给定 $n$ 个单词（ $n\le 20$ ，只含大写或小写字母，长度不超过 20）和一个开头字母，用这些单词拼出一条最长的"龙"。每个单词最多出现两次；相邻两词相连时后缀与前缀的重合部分合并，且重合长度须严格小于两词长度（排除整词包含）。输入第一行一个整数 $n$ ，随后 $n$ 行各一个单词，最后一行为开头字母，输出以此字母开头的最长龙的长度。样例输入 5 / at / touch / cheat / choose / tact / a，样例输出 23。

思路

先预处理 gain[i][j]＝词 $j$ 接在词 $i$ 后的增益（词长减最小合法重叠，接不上记 0），一对词只保留最小重叠——重叠越短本次接出的龙越长，接完后后续只取决于结尾词；再按增益降序枚举后继做 DFS 回溯，每词最多用两次，并以 $slack=\sum_w(2-used_w)(|w|-1)$ 为剩余可增长量上界，满足 当前长度 + slack <= ans 时整枝剪掉。

参考代码

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
60
61
62#!/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-09-30 00:23
# update_at: 2026-09-30 00:23

import sys


def get_gain(a: str, b: str) -> int | None:
    """词 b 接在词 a 后新增的字符数 = 词长 - 最小合法重叠；None 表示接不上。

    合法重叠要求 a 的后缀等于 b 的前缀，且重叠长度 k < 两词长度——
    k 达到任一词长就意味着整词被包含，题面禁止这种相连。
    取最小 k：重叠越短、接出的龙越长，后续只由 b 决定，短重叠严格更优。
    """
    hit = next((k for k in range(1, min(len(a), len(b))) if a[-k:] == b[:k]), None)
    return None if hit is None else len(b) - hit


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)                                # 龙的开头字母
    lens = list(map(len, words))

    # gain[i][j]：词 j 接在词 i 后的增益；nxt[i] 按增益降序，先试长的利于剪枝
    gain = [[get_gain(a, b) for b in words] for a in words]                     # n×n 张表
    nxt = [sorted((j for j, g in enumerate(row) if g),
                  key=row.__getitem__, reverse=True) for row in gain]           # 每行一个候选表

    ans = 0
    used = [0] * word_count
    # 剪枝预算：每词还能接的次数 × (词长-1)，重叠至少吃掉 1 个字符
    slack0 = 2 * sum(l - 1 for l in lens)

    def dfs(last: int, cur: int, slack: int) -> None:
        """以 last 结尾、当前长度 cur 的龙继续往下接；slack 是剩余长度上界。"""
        nonlocal ans
        ans = max(ans, cur)
        if cur + slack <= ans:                        # 剩余潜力追不上当前最优，整枝剪掉
            return
        g = gain[last]
        for j in nxt[last]:
            if used[j] < 2:                           # 每个词最多出现两次
                used[j] += 1
                dfs(j, cur + g[j], slack - (lens[j] - 1))
                used[j] -= 1

    for s, w in enumerate(words):                     # 龙头：取每个以 head 开头的词起步
        if w[0] == head:
            used[s] = 1
            dfs(s, lens[s], slack0 - (lens[s] - 1))
            used[s] = 0

    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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121/**
 * 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-05 05:52
 * update_at: 2026-10-05 05:52
 */
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

const int MAXN = 25; // 单词数上限 20，留出余量

ll n;
string word[MAXN];   // word[i]：第 i 个单词（下标从 1 开始）
ll len[MAXN];        // len[i]：第 i 个单词的长度，不超过 20
ll used[MAXN];       // used[i]：第 i 个单词在龙里已出现的次数，最多 2
ll gain[MAXN][MAXN]; // gain[i][j]：词 j 接在词 i 后新增的字符数，0 表示接不上
ll cand[MAXN][MAXN]; // cand[i]：词 i 的所有可接后继，按增益降序排列
ll cand_cnt[MAXN];   // cand_cnt[i]：词 i 的可接后继个数
char head_char;      // 龙的开头字母
ll ans;              // 当前最长龙的长度

// 计算词 b 接在词 a 后新增的字符数 = |b| - 最小合法重叠，返回 0 表示接不上。
// 合法重叠要求 a 的后缀等于 b 的前缀，且重叠长度严格小于两词长度（排除整词包含）。
// 取最小重叠：接出的龙最长，接完后后续只由 b 决定，所以短重叠严格更优。
ll calc_gain(const string &a, const string &b) {
    ll la = a.size();
    ll lb = b.size();
    ll limit = min(la, lb);
    for (ll k = 1; k < limit; k++) {
        bool match = true;
        for (ll t = 0; t < k; t++) {
            if (a[la - k + t] != b[t]) {
                match = false;
                break;
            }
        }
        if (match) {
            return lb - k;
        }
    }
    return 0;
}

// 以 last 结尾、长度 cur 的龙继续往下接；slack 是剩余单词最多还能贡献的长度上界。
void dfs(ll last, ll cur, ll slack) {
    if (cur > ans) {
        ans = cur;
    }
    if (cur + slack <= ans) {
        return; // 剩余潜力追不上当前最优，整枝剪掉
    }
    for (ll t = 1; t <= cand_cnt[last]; t++) {
        ll j = cand[last][t];
        if (used[j] < 2) {
            used[j]++;
            dfs(j, cur + gain[last][j], slack - (len[j] - 1));
            used[j]--;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    // 剩余长度上界：每个单词每次接上至少被重叠吃掉 1 个字符，单次贡献 <= len-1
    ll slack0 = 0;
    for (ll i = 1; i <= n; i++) {
        slack0 += 2 * (len[i] - 1);
    }

    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= n; j++) {
            gain[i][j] = calc_gain(word[i], word[j]);
        }
    }

    // 候选后继按增益降序：先试接得长的分支，尽快抬高 ans 提高剪枝命中率
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= n; j++) {
            if (gain[i][j] > 0) {
                cand_cnt[i]++;
                cand[i][cand_cnt[i]] = j;
            }
        }
        for (ll x = 1; x <= cand_cnt[i]; x++) {
            for (ll y = x + 1; y <= cand_cnt[i]; y++) {
                if (gain[i][cand[i][y]] > gain[i][cand[i][x]]) {
                    ll tmp = cand[i][x];
                    cand[i][x] = cand[i][y];
                    cand[i][y] = tmp;
                }
            }
        }
    }

    ans = 0;
    // 龙头：枚举所有以开头字母打头的单词作为第一个词
    for (ll s = 1; s <= n; s++) {
        if (word[s][0] == head_char) {
            used[s] = 1;
            dfs(s, len[s], slack0 - (len[s] - 1));
            used[s] = 0;
        }
    }

    cout << ans << "\n";
    return 0;
}

目录

题目描述

思路

参考代码