T4 接龙（chain）

答案解析

解题思路

本文的解题思想为dp。

dp[r][x]：接龙 r 轮、以 x 结尾的状态：

dp[r][x] = -1：不可实现。

dp[r][x] = i（一个自然数）：可以通过词库 i 实现（最后一次接龙操作使用的是词库 i 中的某个连续子序列）。

dp[r][x] = -2：可以通过多个词库实现。

代码解析

完整的求解部分：

vector<vector<int> > Solve(int mx) {
    vector<vector<int> > dp(R, vector<int>(mx + 5, -1));
    dp[0][1] = -2;
    for (int r = 1; r <= 100; r++) {
        for (int i = 1; i <= n; i++) {
            int lst = -1;
            for (int j = 0; j < s[i].size(); j++) {
                int tmp = s[i][j];
                if (lst != -1 && j - lst + 1 <= k) {
                    if (dp[r][tmp] == -1)
                        dp[r][tmp] = i;
                    else if (dp[r][tmp] != i)
                        dp[r][tmp] = -2;
                }

                if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
                    lst = j;
            }
        }
    }
    return dp;
}

 

逐行分析

mx：所有词库中的最大值，用于构建dp的第二个维度。

dp的大小为R(最大轮数) * mx(所有词库中的最大值)。

vector<vector<int> > Solve(int mx) {
	vector<vector<int> > dp(R, vector<int>(mx + 5, -1));

dp[0][1] = -2：作为虚拟起点，使得第一次接龙可以从数字 1 开始。

dp[0][1] = -2;

r：轮数。

i：尝试让第 i 个人接龙。

j：第 i 个人词库中第 j 个词语。

lst：当前序列 i 中最近一个满足接龙条件的起始位置（可以以lst为起点开始接龙）。

for (int r = 1; r <= 100; r++) {
        for (int i = 1; i <= n; i++) {
            int lst = -1;
            for (int j = 0; j < s[i].size(); j++) {
            }
        }
    }

 

获取当前人员 i 的词库中第 j 个词语。

如果当前词库中有一个合适的起点可以开始接龙，并且长度合适：

那么选择子序列[lst, j]开始接龙。

更新当前状态。

如果上一轮接龙不是 i 在接龙，并且可以以tmp结束，那么这一轮也可以从tmp开始接龙。

int tmp = s[i][j];
if (lst != -1 && j - lst + 1 <= k) {
    if (dp[r][tmp] == -1)
        dp[r][tmp] = i; // 首次发现路径则记录序列i
    else if (dp[r][tmp] != i)
        dp[r][tmp] = -2; // 若已有其他序列可达则标记为多路径(-2)
}

if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
    lst = j;