题解：P14732 [ICPC 2022 Seoul R] Shuffle Game

ziben · 2026-08-10 18:47:16 · 题解

题意简述

给定序列 X，还有两个序列 P_1、P_2。我们可以把 P_1、P_2 交错合并得到序列 Y，合并时不能打乱 P_1、P_2 内部元素的先后顺序。求所有合法的 Y 和 X 的最长公共子序列的最大长度。

最长公共子序列（LCS）：元素不需要连续，但相对先后顺序必须保持一致。

数据范围：3 \le n \le 500。

题目分析

如果暴力生成全部合并后的 Y，合并方案的数量极大，一定会超时，因此我们使用动态规划解决本题。

状态设计

设 dp[i][j][L]：使用了 P_1 的前 i 个元素、P_2 的前 j 个元素，可以凑出长度为 L 的公共子序列。数组存储的值是这个子序列在 X 当中结束的最小下标。

为什么保存最小下标？ 同样是长度为 L 的公共子序列，结束位置越靠前，X 剩下未使用的字符就越多，后续就更容易匹配更多字符。

预处理 \operatorname{nxt} 数组

2. 不选取 P_2[j]，继承上一状态：dp[i][j][L] \gets \min(dp[i][j][L], dp[i][j-1][L])

3. 使用 P_1[i] 进行匹配。若 t = dp[i-1][j][L] \ne \text{INF}，查询得到新位置 \mathit{newpos}：

   dp[i][j][L+1] \gets \min(dp[i][j][L+1], \mathit{newpos})

4. 使用 P_2[j] 进行匹配，逻辑同上：

   dp[i][j][L+1] \gets \min(dp[i][j][L+1], \mathit{newpos})

初始条件与答案

初始条件：dp[0][0][0] = 0，其余全部赋值为无穷大 \text{INF}。 从大到小枚举 L，第一个满足 dp[p][q][L] < \text{INF} 的 L 就是本题答案。

复杂度分析

预处理 \operatorname{nxt} 数组：O(n^2)。 DP 时间复杂度：O(n^3)，n=500，运算量约 1.25 \times 10^8，C++ 将三维数组定义在全局可以通过时限。

注意：三维数组一定要写在全局，写在 main 函数内部会栈溢出导致 RE。

题醒：本人已错不知多少次，代码仅供参考。

（题解由本人和家人研究而出，可能有错误和逻辑不对的地方，请以题目为基准。）

代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
using namespace std;

const int MAXN = 505;
const int INF = 1e9;

vector<unordered_map<string, int>> nxt;
int dp[MAXN][MAXN][MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, p, q;
    cin >> n >> p >> q;

    vector<string> X(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> X[i];
    vector<string> P1(p + 1);
    for (int i = 1; i <= p; ++i)
        cin >> P1[i];
    vector<string> P2(q + 1);
    for (int i = 1; i <= q; ++i)
        cin >> P2[i];

    nxt.resize(n + 2);
    unordered_map<string, int> mp;
    for (int pos = n; pos >= 0; --pos)
    {
        if (pos + 1 <= n)
        {
            mp[X[pos + 1]] = pos + 1;
        }
        nxt[pos] = mp;
    }

    for (int i = 0; i <= p; ++i)
        for (int j = 0; j <= q; ++j)
            for (int l = 0; l <= n; ++l)
                dp[i][j][l] = INF;
    dp[0][0][0] = 0;

    for (int i = 0; i <= p; ++i)
    {
        for (int j = 0; j <= q; ++j)
        {
            if (i == 0 && j == 0) continue;
            if (i > 0)
            {
                for (int len = 0; len <= n; ++len)
                {
                    dp[i][j][len] = min(dp[i][j][len], dp[i - 1][j][len]);
                }
            }
            if (j > 0)
            {
                for (int len = 0; len <= n; ++len)
                {
                    dp[i][j][len] = min(dp[i][j][len], dp[i][j - 1][len]);
                }
            }
            if (i > 0)
            {
                for (int len = 0; len < n; ++len)
                {
                    int t = dp[i - 1][j][len];
                    if (t == INF) continue;
                    string c = P1[i];
                    if (nxt[t].count(c))
                    {
                        int newpos = nxt[t][c];
                        dp[i][j][len + 1] = min(dp[i][j][len + 1], newpos);
                    }
                }
            }
            if (j > 0)
            {
                for (int len = 0; len < n; ++len)
                {
                    int t = dp[i][j - 1][len];
                    if (t == INF) continue;
                    string c = P2[j];
                    if (nxt[t].count(c))
                    {
                        int newpos = nxt[t][c];
                        dp[i][j][len + 1] = min(dp[i][j][len + 1], newpos);
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int l = n; l >= 0; --l)
    {
        if (dp[p][q][l] < INF)
        {
            ans = l;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

 AI 贡献说明：
题解使用 AI 排版润色。核心思路、推导过程、代码均为个人完成。