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

发表评论

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

你是机器人吗? =。= *