题解：P1019 [NOIP 2000 提高组] 单词接龙

源题目地址：https://www.luogu.com.cn/problem/P1019

题目分析

这道题目要求我们构建一个最长的单词接龙，每个单词最多使用两次，且相邻单词不能完全包含。我们需要找到以给定字母开头的最长单词链。

解题思路

1. 预处理重叠部分：计算每对单词之间的最大重叠长度。
2. 深度优先搜索（DFS）：从所有以给定字母开头的单词开始，尝试构建最长的单词链。
3. 使用次数限制：记录每个单词的使用次数，确保不超过两次。
4. 长度更新：在每次成功连接单词后，更新当前最长单词链的长度。

代码实现

import java.util.Scanner;

public class Main {
    static int n; // 单词数量
    static String[] words; // 存储所有单词
    static int[] used; // 记录每个单词的使用次数
    static int[][] overlap; // 记录单词间的重叠长度
    static int maxLength = 0; // 最长单词链长度

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符
        words = new String[n];
        used = new int[n];
        overlap = new int[n][n];
        
        // 读取所有单词
        for (int i = 0; i < n; i++) {
            words[i] = scanner.nextLine();
        }
        String startChar = scanner.nextLine(); // 起始字母
        
        // 预处理计算每对单词间的重叠长度
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 计算单词i和单词j的最大重叠长度
                for (int k = 1; k < Math.min(words[i].length(), words[j].length()); k++) {
                    if (words[i].substring(words[i].length() - k).equals(words[j].substring(0, k))) {
                        overlap[i][j] = k;
                        break;
                    }
                }
            }
        }
        
        // 从所有以startChar开头的单词开始DFS
        for (int i = 0; i < n; i++) {
            if (words[i].charAt(0) == startChar.charAt(0)) {
                used[i]++;
                dfs(i, words[i].length());
            }
        }
        
        System.out.println(maxLength);
    }

    // 深度优先搜索构建单词链
    static void dfs(int currentWord, int currentLength) {
        // 更新最大长度
        if (currentLength > maxLength) {
            maxLength = currentLength;
        }
        
        // 尝试连接所有可能的单词
        for (int i = 0; i < n; i++) {
            // 检查是否可以连接（有重叠且使用次数不超过两次）
            if (overlap[currentWord][i] > 0 && used[i] < 2) {
                used[i]++;
                // 计算新长度：当前长度 + 新单词长度 - 重叠部分
                dfs(i, currentLength + words[i].length() - overlap[currentWord][i]);
                used[i]--; // 回溯
            }
        }
    }
}

复杂度分析

• 时间复杂度：O(n^2 + n!)，其中n是单词数量。预处理重叠部分为O(n^2)，DFS最坏情况下为O(n!)。
• 空间复杂度：O(n^2)，用于存储单词间的重叠长度。

算法特点

1. 预处理优化：提前计算单词间的重叠长度，减少DFS中的重复计算。
2. DFS遍历：确保能够探索所有可能的单词连接方式。
3. 使用次数限制：通过used数组控制每个单词的使用次数。
4. 实时更新长度：在每次成功连接后立即更新最长长度。

该解法能够高效处理题目给定的数据规模（n ≤ 20）。对于更大的数据规模，可能需要更优化的算法或剪枝策略。