题解：P12738 [POI 2016 R2] 口吃 Stutter

· · 题解

首先考虑一个时空复杂度都是 O(n^2) 的做法：

首先求出 a_i,b_i 中的每一个数下一次的出现位置 nxta_i,nxtb_i。类似于正常的 LCS，设 dp_{i,j} 为考虑 a 的前 i 项，b 的前 j 项的最长公共口吃序列长度，考虑向后转移，显然有以下转移：

由于空间限制只有 32MB，而当前的状态转移又无法进行滚动数组优化，考虑重新设计状态。

仔细分析转移过程，考虑如何将第二步写成能够滚动数组优化的形式。现在的转移过程是 i\to nxta_{i+1}，j\to nxtb_{j+1}，不如我们先将 j 一步移动到 nxtb_{j+1}，并对当前状态进行标记，代表 i 目前只匹配了一次，在转移的过程中，不断将 i 往右移，不改变 j 的值，直到发现 a_i=b_j（此时的 j 就相当于原来的 nxtb_{j+1}），完成一次匹配。

这样我们只会从 dp_i 转移到 dp_{i+1}，可以使用滚动数组优化。具体的转移可以参考代码。其中的一个细节是，若发现 a_{i+1}=b_{j+1}，我们只能将 dp_{i+1,nxtb_{j+1},1} 更新，但是此时 a_{i+1}=b_{nxtb_{j+1}}，因此我们完成匹配时判断的是 a_{i+1} 和 b_j 是否相等。

::::info[AC 代码] Submission

#include <bits/stdc++.h>
using namespace std;
int n, m, a[16000], b[16000], nxta[16000], nxtb[16000], pre[16000][2], dp[16000][2], nxt[16000][2];
map<int, int> mp;
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
        cin >> b[i];
    for (int i = m; i >= 1; i--) {
        if (mp[b[i]]) nxtb[i] = mp[b[i]];
        mp[b[i]] = i;
    }
    for (int i = 0; i <= m; i++)
        pre[i][1] = -0x3f3f3f3f;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++)
            dp[j][0] = dp[j][1] = -0x3f3f3f3f;
        for (int j = 0; j <= m; j++) {
            pre[j + 1][0] = max(pre[j + 1][0], pre[j][0]);
            dp[j][0] = max(dp[j][0], pre[j][0]);
            if (a[i + 1] == b[j + 1] && nxtb[j + 1]) dp[nxtb[j + 1]][1] = max(dp[nxtb[j + 1]][1], pre[j][0]);
            if (a[i + 1] == b[j]) dp[j][0] = max(dp[j][0], pre[j][1] + 2);
            else dp[j][1] = max(dp[j][1], pre[j][1]);
        }
        for (int j = 0; j <= m; j++)
            pre[j][0] = dp[j][0], pre[j][1] = dp[j][1];
    }
    cout << max(pre[m][0], pre[m][1]);
    return 0;
}

::::