题解：P2679 [NOIP 2015 提高组] 子串

wNightOvO · 2025-03-21 13:47:48 · 题解

P2679 [NOIP 2015 提高组] 子串

题目

给出两个字符串 A 和 B，在 A 中取出 k 个互不重叠的子串，使得这些子串按顺序拼接在一起时等于 B，求方案数。

状态

一看是神秘的方案题，很容易想到 dp。为了方便，可以用数组 a 和 b 存下 A 和 B 的 ASCII 码方便转移和优化复杂度，这样做是正确的原因是只关注两个字符是否相等而不是其他性质。

我们可以令 f_{i,j,t} 表示此时枚举数组 a 前 i-1 都已算完，到第 i 项，枚举数组 b 前 j-1 项都已算完，到第 j 项，还可以取出 t 个子串时的状态。

这是常规的设计状态的思路，但我们很快发现，这样设计时不好辨别选取该项时是不是和上一个选的是同一个子串，于是我们便要增加维度。

令 f_{i,j,t,0/1}，其中 i，j，t 意思同上，0 表示不取数组 a 中的第 i 项，1 表示取。

容易发现，该状态可以在转移的时候进行判断，于是就可以开始状态转移。

转移

转移的时候进行分类讨论。

当 i > j 时，f_{i,j,t,0} = f_{i,j,t,1} = 0。
当 a_{i} \ne b_{j} 时，i 不能匹配 j，只能从前面的状态进行转移，即：

\Large{f_{i,j,t,0} = f_{i-1,j,t,0} + f_{i-1,j,t,1}}

当 a_{i} = b_{j} 时，可以用 a_{i} 匹配 b_{j}，此时要么 i-1 的选了可以成为一个子串，要么新开一个子串，即：

\Large{f_{i,j,t,0} = f_{i-1,j,t,0} + f_{i-1,j,t,1}} \\ \Large{f_{i,j,t,1} = f_{i-1,j-1,t,1} + f_{i-1,j-1,t-1,0} + f_{i-1,j-1,t-1,1}}

Code

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

typedef long long LL;

const int N = 1e3+1 , M = 201 , inf = 1e9+7;

int n , m , k , a[N] , b[M];

LL f[N][M][M][2];

string in;

int main()
{
    ios::sync_with_stdio (false);

    cin >> n >> m >> k;

    cin >> in;

    for(int i = 1 ; i <= n ; i ++)
    {
        a[i] = in.at(i-1) - 'a' + 1;
    }

    cin >> in;

    for(int i = 1 ; i <= m ; i ++)
    {
        b[i] = in.at(i-1) - 'a' + 1;
    }

    f[0][0][0][0] = 1;

    for(int i = 1 ; i <= n ; i ++)
    {
        f[i][0][0][0] = 1;
        for(int j = 1 ; j <= m && j <= i ; j ++)
        {
            for(int t = 1 ; t <= k ; t ++)
            {
                f[i][j][t][0] = (f[i-1][j][t][0] + f[i-1][j][t][1]) % inf;
                if(a[i] == b[j])
                {
                    f[i][j][t][1] = (f[i-1][j-1][t][1] + f[i-1][j-1][t-1][0] + f[i-1][j-1][t-1][1]) % inf;
                }           
            }
        }
    }

    cout << (f[n][m][k][0] + f[n][m][k][1]) % inf << "\n";

    return 0;
}

然而，只有 10 分。

这么大的空间 1000 \times 200 \times 200 \times 2 = 8 \times 10^7 谁不迷糊。

可以发现每个状态的 i 只依赖于 i-1，于是可以滚动数组优化。

用取模运算或交替覆盖方式访问滚动数组。这里取模 2 可以近似看作位运算 &。

AC Code

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

typedef long long LL;

const int N = 1e3+1 , M = 201 , inf = 1e9+7;

int n , m , k , a[N] , b[M];

LL f[2][M][M][2];

string in;

int main()
{
    ios::sync_with_stdio (false);

    cin >> n >> m >> k;

    cin >> in;

    for(int i = 1 ; i <= n ; i ++)
    {
        a[i] = in.at(i-1) - 'a' + 1;
    }

    cin >> in;

    for(int i = 1 ; i <= m ; i ++)
    {
        b[i] = in.at(i-1) - 'a' + 1;
    }

    f[0][0][0][0] = f[1][0][0][0] = 1;

    for(int i = 1 ; i <= n ; i ++)
    {
        for(int j = 1 ; j <= m && j <= i ; j ++)
        {
            for(int t = 1 ; t <= k ; t ++)
            {
                f[i&1][j][t][0] = (f[(i-1)&1][j][t][0] + f[(i-1)&1][j][t][1]) % inf;
                if(a[i] == b[j])
                {
                    f[i&1][j][t][1] = (f[(i-1)&1][j-1][t][1] + f[(i-1)&1][j-1][t-1][0] + f[(i-1)&1][j-1][t-1][1]) % inf;
                }
                else f[i&1][j][t][1] = 0;
        // 这里注意，因为把数组复用了，转移不了的要清零。
            }
        }
    }

    cout << (f[n&1][m][k][0] + f[n&1][m][k][1]) % inf << "\n";

    return 0;
}