CF578D LCS Again 题解

题目链接：CF578D LCS Again

题意：

给定一个字符串 $S$，求有多少个与 $S$ 等长字符串 $T$，满足 $\mathrm{LCS}(S,T)=|S|-1$，其中 $S,T$ 只包含前 $m$ 个小写字母。

LCS（最长公共子序列）

输入格式：

第一行包括两个数字 $n$ 和 $m$，第二行是给定的字符串 $S$。

输出格式：

输出一行一个整数表示答案。

一眼hash，然后发现假了。。。

这里就讲讲dp套dp解法，其他解法可以看这篇博客

考虑经典的LCS（最长公共子序列）

$f_{i,j}$ 表示第一个串前 $i$ 个字符和第二个串前 $j$ 个字符的最长公共子序列

显然 $f_{i,j}$ 只与 $f_{i-1,j},f_{i,j-1},f_{i-1,j-1}$ 有关

而我们要求的就是 $f_{i,j}=n-1$ 的方案数

从 $f_{i,j}=n-1$ 可以得到

$$\min \{i,j\} -1 \le f_{i,j} \le \min \{ i,j\}$$

因此，我们指关心所有满足 $|i-j| \le 1$ 的 $j$

即 $f_{i,i-1},~f_{i,i},~f_{i,i+1}$ 这三个，并且显然有

$$i-2 \le f_{i,i-1} \le i-1 \\i-1 \le f_{i,i} \le i \\i-1 \le f_{i,i+1} \le i$$

所以dp值的组合一共有 $2^3 = 8$ 种情况

考虑状压，设状态为 $P$ 。那么有什么用呢？

设 $g_{i,P}$ 表示有多少个 $T$ 的 $i$-前缀，满足上述 $3$ 个dp值的状态为 $P$

接着枚举 $m$ 个字符，分别与 $s_i,s_{i+1},s_{i+2}$ 比较，然后转移就好啦

最后答案就是符合条件 $f_{i,j}=n-1$ 的那几个状态

时间复杂度 $O(nm)$

代码：（跟讲述里的变量名不太一样）

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e5+15))

char s[N];
int n,m,p,f[N][8],q[3],nq[3];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> (s+1);
    for(int i=1; i<=n; i++) s[i] = s[i] - 'a' + 1;
    for(int i=1; i<=m; i++) 
    {
        p=1;
        if(i==s[1]) p |= 2;
        if(i==s[1] || i==s[2]) p |= 4;
        ++f[1][p];
    }
    for(int i=1; i<n; i++)
        for(int j=0; j<=7; j++)
        {
            if(!f[i][j]) continue;
            q[0] = i-2 + (j & 1);
            q[1] = i-1 + ((j >> 1) & 1);
            q[2] = i-1 + ((j >> 2) & 1);
            for(int k=1; k<=m; k++)
            {
                nq[0] = (k==s[i] ? q[0]+1 : q[1]);
                nq[1] = (k==s[i+1] ? q[1]+1 : max(nq[0], q[2]));
                nq[2] = (k==s[i+2] ? q[2]+1 : nq[1]);
                if(nq[0] < i-1 || nq[1] < i || nq[2] < i) continue;
                p = nq[0] - (i-1);
                p |= (nq[1] - i) << 1;
                p |= (nq[2] - i) << 2;
                f[i+1][p] += f[i][j];
            }
        }
    cout << (f[n][0] + f[n][1] + f[n][4] + f[n][5]) << '\n';
    return 0;
}

参考文献：

[1] https://yhx-12243.github.io/OI-transit/records/cf578D.html