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