1. 题目

传送门= ̄ω ̄=

2. 题解

首先不难想到:
设 $f[i][j][k]$为第一个字符串的前 i 个字符和第二个字符串的前 j 个字符匹配,用了 k 个子串时的方案数。
那么 $f[i][j][k]=f[i-1][j-1][k]+f[i-1][j-1][k-1]$,$f[i-1][j-1][k]$表示不新建一个子串,$f[i-1][j-1][k-1]$表示新建一个子串
然而我们发现,这样处理第 i 个字符必然会被选择,也就是我们少处理了很多状态。
那么我们分情况讨论。
新建一维,状态变为 4 维,第 4 维为 0 或 1,表示第 i 个字符选或者不选。
则:
1. 第 i 个字符不选:那上一个状态要么选择了第 i-1 个字符,要么没选择第 i-1 个字符。
2. 第 i 个字符要选:那上一个状态要么没选择第 i-1 个字符,那现在必须新建一个子串;要么选择了第 i-1 个字符,可以新建子串,也可以不新建。这种情况需要满足第 i 个字符和第 j 个字符相同

所以状态转移方程:
$$f[i][j][l][0]=f[i-1][j][l][0]+f[i-1][j][l][1]$$
$$f[i][j][l][1]=f[i-1][j-1][l-1][0]+f[i-1][j-1][l-1][1]+f[i-1][j-1][l][1]$$

另:注意开 long long

代码:

#include <bits/stdc++.h>
#define MOD (1000000007ll)
using namespace std;
typedef long long LL;
LL n,m,k,f[2][205][205][2],cnt;
char s1[1005],s2[205];
int main()
{
    scanf("%lld%lld%lld%s%s",&n,&m,&k,s1+1,s2+1);
    for(LL i=1;i<=n;i++)
    {
        f[i&1][1][1][0]=cnt;
        if(s1[i]==s2[1])f[i&1][1][1][1]=1,cnt++;
        for(LL j=2;j<=m;j++)
            for(LL l=1;l<=k;l++)
            {
                f[i&1][j][l][0]=(f[(i&1)^1][j][l][0]+f[(i&1)^1][j][l][1])%MOD;
                if(s1[i]==s2[j])
                    f[i&1][j][l][1]=
                        (f[(i&1)^1][j-1][l][1]
                        +f[(i&1)^1][j-1][l-1][0]
                        +f[(i&1)^1][j-1][l-1][1])%MOD;
            }
        for(LL j=1;j<=m;j++)
            for(LL l=1;l<=k;l++)
                f[(i&1)^1][j][l][0]=f[(i&1)^1][j][l][1]=0;
    }
    printf("%lld\n",(f[n&1][m][k][0]+f[n&1][m][k][1])%MOD);
    return 0;
} 
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注