题解：P8020 [ONTAK2015] Badania naukowe

· · 题解

注意到我们要求答案一定存在 C 这个子串。

因此，我们考虑枚举 C 是在 A,B 的哪一个位置出现的。

我们使用 P(i) 表示从 A_i 开始匹配 C，到最后一个字符的下标 j，图解：

\begin{aligned} \begin{aligned} i\kern{11.5ex}j\kern{1.7ex} \end{aligned}\\[-1ex] \begin{array}{l:l} A&\texttt{x\dots axbxxcdxxxe}\\ C&\kern{4ex}\boxed{\texttt{a\ b\ \ cd\ \ \ e}} \end{array} \end{aligned}

同理，使用 Q(i) 表示从 B_i 开始匹配 C，最后一个字符的下标 j。

于是，我们枚举 i,j 分别表示 C 从 A_i,B_j 开始。

那么，如果从 i,j 开始可以匹配到完整的 C 字符串，那么这个状态就是合法的。

考虑如何表示答案？

设 F(i,j) 表示 A[1,i] 和 B[1,j] 的 LCS（最长公共子序列）。

设 G(i,j) 表示 A[i,n] 和 B[j,m] 的 LCS（最长公共子序列）。

那么，答案可以表示为，

\max_{i,j}\{ F(i-1,j-1)+G(P(i)+1,Q(j)+1)+\lvert C\rvert, \text{if $\langle i,j\rangle$ is valid.} \}

也就是前面的和后面的 LCS 可以直接计入答案，再加上子串 C 的长度。

如何求 LCS（最长公共子序列）。

以 F(i,j) 为例，有状态转移方程，

F(i,j)=\begin{cases} F(i-1,j-1)+1&A_i=B_j\\ \max\{F(i,j-1),F(i-1,j)\}&A_i\neq B_j \end{cases}

表示如果相同，则加入 LCS，否则删去一个继续匹配。

反过来，

G(i,j)=\begin{cases} G(i+1,j+1)+1&A_i=B_j\\ \max\{G(i,j+1),G(i+1,j)\}&A_i\neq B_j \end{cases}

同理的。

合起来就行了，核心代码：

constexpr int N = 3e3 + 10;

void init_matching(int n, int *A, int k, int *C, int *P) {
    for (int i = 1; i + k - 1 <= n; ++i) {
        int p = i, q = 1;
        while (p <= n && q <= k) {
            q += (A[p] == C[q]);
            ++p;
        }
        P[i] = (q > k) ? p - 1 : 0;
    }
}

int n, A[N], P[N];
int m, B[N], Q[N];
int k, C[N];
int F[N][N], G[N][N];

void init_LCS() {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (A[i] == B[j])
                F[i][j] = F[i - 1][j - 1] + 1;
            else
                F[i][j] = max(F[i][j - 1], F[i - 1][j]);
}

void init_rLCS() {
    for (int i = n; i >= 1; --i)
        for (int j = m; j >= 1; --j)
            if (A[i] == B[j])
                G[i][j] = G[i + 1][j + 1] + 1;
            else
                G[i][j] = max(G[i][j + 1], G[i + 1][j]);
}

int get_ans() {
    int Ans = -1;
    for (int i = 1; i + k - 1 <= n; ++i)
        for (int j = 1; j + k - 1 <= m; ++j)
            if (P[i] && Q[j])
                Ans = max(Ans, F[i - 1][j - 1] + G[P[i] + 1][Q[j] + 1] + k);
    return Ans;
}

void Main() {
    cin >> n;
    copy_n(istream_iterator<int>(cin), n, A + 1);
    cin >> m;
    copy_n(istream_iterator<int>(cin), m, B + 1);
    cin >> k;
    copy_n(istream_iterator<int>(cin), k, C + 1);
    init_matching(n, A, k, C, P);
    init_matching(m, B, k, C, Q);
    init_LCS(), init_rLCS();
    cout << get_ans() << endl;
}