【动态规划】P10694 [SNCPC2024] 双子序列

· · 题解

对于任意一个满足要求（即子序列中包含 S_1,S_2 两个模式串）的子串，假设其第一个数出现在 S 的第 l 个字符，最后一个数出现在 S 的第 r 个字符（下标从 1 开始），则包含这个子串的子串个数为 l\times (\lvert S \rvert-r+1)。我们可以枚举右端点，那么需要计算的便是满足要求的子串左端点之和。

动态规划，记 f_{i,j,k} 表示以第 i 个字符为最小的右端点，匹配到串 S_1 的第 j 位，S_2 的第 k 位的符合条件左端点之和。那么得到转移：

但是枚举转移单次 O(\lvert S \rvert)，总复杂度是 O({\lvert S \rvert}^2 \lvert S_1\rvert\lvert S_2\rvert)。因此可以枚举右端点时，将后面的 \displaystyle \sum_{t=1}^{i-1} f_{t,j,k} 前缀和出来。即可实现单次 O(1) 转移，总复杂度 O(\lvert S \rvert \lvert S_1\rvert\lvert S_2\rvert)。

:::success[AC 代码]

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
const int maxm = 25;
int n, len1, len2;
string s, s1, s2;
long long dp[maxn][maxm][maxm], pre[maxm][maxm], ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s >> s1 >> s2;
    n = s.length();
    len1 = s1.length();
    len2 = s2.length();
    s = " " + s;
    s1 = " " + s1;
    s2 = " " + s2;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == s1[1])
            dp[i][1][0] = i;
        if (s[i] == s2[1])
            dp[i][0][1] = i;
        if (s[i] == s1[1] && s[i] == s2[1])
            dp[i][1][1] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= len1; j++)
        {
            for (int k = 0; k <= len2; k++)
            {
                pre[j][k] = (pre[j][k] + dp[i - 1][j][k]) % mod;
            }
        }
        for (int j = 0; j <= len1; j++)
        {
            for (int k = 0; k <= len2; k++)
            {
                if (j > 0 && s1[j] == s[i])
                    dp[i][j][k] = (dp[i][j][k] + pre[j - 1][k]) % mod;
                if (k > 0 && s2[k] == s[i])
                    dp[i][j][k] = (dp[i][j][k] + pre[j][k - 1]) % mod;
                if (j > 0 && k > 0 && s1[j] == s[i] && s2[k] == s[i])
                    dp[i][j][k] = (dp[i][j][k] + pre[j - 1][k - 1]) % mod;
            }
        }
        ans = (ans + dp[i][len1][len2] * (n - i + 1)) % mod;
    }
    cout << ans << "\n";
    return 0;
}

代码经过了格式化。 :::