[CF1499E] Chaotic Merge - dp

[CF1499E] Chaotic Merge - dp

Description

给定两个仅由小写字母组成的字符串 \(x\) 和 \(y\)。如果一个序列仅包含 \(|x|\) 个 \(0\) 和 \(|y|\) 个 \(1\)，则称这个序列为合并序列。若一个字符串任意两个相邻位置上的字符都不同，则我们称该字符串是混乱的。定义 \(f(l_1,r_1,l_2,r_2)\) 表示能从 \(x\) 的子串 \(x[l_1,r_1]\) 和 \(y\) 的子串 \(y[l_2,r_2]\) 生成混乱的字符串的不同的合并序列的数量，要求子串非空。求 \(\sum \limits_{1 \le l_1 \le r_1 \le |x| , 1 \le l_2 \le r_2 \le |y|} f(l_1, r_1, l_2, r_2)\)

Solution

先不考虑选子串，先考虑整个串，设 \(f[i][j][0/1]\) 表示取了 \(x[1..i], y[1..j]\) 进行合并，最后一个字符是 \(x[i]\) 还是 \(y[j]\)，此时的方案数是多少

现在把子串的问题带进来，右端点实际上已经包含在我们的状态中了，所以我们实际需要考虑的是左端点

考虑在先前的版本上做点修改，状态设计不变，对每个状态，额外引入一个从这里开始一个新的串（即一边长度为 \(1\)）的方案数

细节需要调教一下

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1005;
const int mod = 998244353;

int f[N][N][2], fx[N], fy[N], n, m;

string x, y;

signed main()
{
    ios::sync_with_stdio(false);
    cin >> x >> y;
    x = " " + x;
    y = " " + y;
    string &a = x;
    string &b = y;

    n = x.length() - 1;
    m = y.length() - 1;

    int ans = 0;

    for (int i = 1; i <= n; i++)
    {
        if (a[i] != a[i - 1])
            f[i][0][0] = f[i - 1][0][0] + 1;
        else
            f[i][0][0] = 1;
    }

    for (int j = 1; j <= m; j++)
    {
        if (b[j] != b[j - 1])
            f[0][j][1] = f[0][j - 1][1] + 1;
        else
            f[0][j][1] = 1;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (i > 1 && a[i] != a[i - 1])
                f[i][j][0] += f[i - 1][j][0];
            if (i > 1 && a[i] != b[j])
                f[i][j][0] += f[i - 1][j][1];
            if (j > 1 && a[i] != b[j])
                f[i][j][1] += f[i][j - 1][0];
            if (j > 1 && b[j] != b[j - 1])
                f[i][j][1] += f[i][j - 1][1];
            if (a[i] != b[j])
            {
                f[i][j][0] += f[0][j][1];
                f[i][j][1] += f[i][0][0];
            }
            f[i][j][0] %= mod;
            f[i][j][1] %= mod;
            ans += f[i][j][0];
            ans += f[i][j][1];
            ans %= mod;
        }
    }
    cout << ans << endl;
}

[CF1499E] Chaotic Merge - dp

原文：https://www.cnblogs.com/mollnn/p/14603853.html