洛谷2679 子串

题意

有 $A,B$ 两个字符串，要从 $A$ 中选出 $k$ 个子串，按原顺序排列后形成 $B$ 。求方案数。

$A,B$ 的长度为 $N,M$ ，$N\le 1000 \ , \ M\le 200$ 。

题解

用 $f[i][j][k]$ 表示取到 $A_i,B_j$ ，选了 $k$ 个子串的方案数。可以枚举当前子串的长度 $l$ ，这样要求 $A_{[i-l+1,i]}$ 和 $B_{[j-l+1,j]}$ 完全匹配。显然 $A$ 中取的上一个位置可以在 $[1,i-l]$ 中任选，方程式为：

$$f[i][j][k] = \sum_l \sum_{p=1}^{i-l} f[p][j-l][k-1]$$

$p$ 可以用前缀和优化掉，用 $g[i][j][k]$ 表示关于 $i$ 的前缀和，则方程式可化为：

$$f[i][j][k] = \sum_l g[i-l][j-l][k-1]$$

这样每次枚举 $l$ 时间会爆炸。可以发现当 $A_i=B_j$ 时， $f[i][j][k]$ 比 $f[i-1][j-1][k]$ 多了 $g[i-1][j-1][k-1]$ ，方程式化为：

$$f[i][j][k] = \begin{cases} 0 \ (A_i \neq B_j) \\ f[i-1][j-1][k] + g[i-1][j-1][k-1] \ (A_i = B_j) \end{cases}$$

时间没问题了，但空间还是会爆，所以用滚动数组优化。

#include<bits/stdc++.h>
#define ha 1000000007

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

char x[1005],y[205];
int n,m,k,f[205][205],g[205][205];

signed main()
{
    n=read(); m=read(); k=read();
    scanf("%s%s",x+1,y+1);
    g[0][0]=1;
    for (int i=1;i<=n;i++)
    {
        for (int j=min(i,m);j;j--)
        {
            for (int l=min(k,j);l;l--)
            {
                if (x[i]==y[j]) f[j][l]=(f[j-1][l]+g[j-1][l-1])%ha;
                else f[j][l]=0;
                g[j][l]=(g[j][l]+f[j][l])%ha;
            }
        }
    }
    return !printf("%d",g[m][k]);
}