洛谷2679 子串

Luogu

算法

这是一道DP题。

自然想到用$f[i] [j] [k]$来表示A、B的前i、j个字符分k串的方案数。

所以$f[i] [j] [k]=f[i-1] [j-1] [k-1]+f[i-1] [j-1] [k](a[i]==b[j])$

但是这样是不行的,因为你并没有考虑所有情况。

所以要设$s[i] [j] [k]$来表示A、B的前i、j个字符分k串,并且一定用了A[i]的方案数,再设$f[i][j][k]$表示A、B的前i、j个字符分k串的方案总数。

所以当$a[i]==b[j]$时,$s[i][j][k]$有两种决策:放在前面的子串或新开一个子串。
所以:

$s[i][j][k]=(s[i-1][j-1][k]+f[i-1][j-1][k-1])\quad(a[i]==b[j])$

否则若$a[i]\neq b[j]$,则$s[i] [j] [k]=0$。
然后把方案数加起来:

$f[i][j][k]=(f[i-1][j-1][k]+s[i][j][k])$

最后的答案为$f[n] [m] [k]$,边界为$f[0] [0] [0]=1$。
注意到空间问题,所以把第一维滚动。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
int s[2][1001][1001]; //t[i][j][k]表示A、B的前i、j个字符分k串,并且一定用了A[i]的方案数 
int f[2][1001][1010]; //f[i][j][k]表示A、B的前i、j个字符分k串,不一定用了A[i]的方案数
char a[1010],b[1010];
const int MOD=1000000007; //模数
int main()
{
    int n,m,k;
    scanf("%d%d%d\n",&n,&m,&k);
    scanf("%s",a+1); scanf("%s",b+1); //输入
    int now=1,last=0; //滚动数组用
    f[0][0][0]=1; //边界
    for (re int i=1;i<=n;i++) //DP
    {
        f[now][0][0]=1; //边界
        for (re int j=1;j<=m;j++)
            for (re int p=1;p<=k;p++) //上面说的状态转移↓
            {
                if (a[i]==b[j]) s[now][j][p]=(s[last][j-1][p]+f[last][j-1][p-1])%MOD;
                else s[now][j][p]=0;
                f[now][j][p]=(f[last][j][p]+s[now][j][p])%MOD;
            }
        now=!now; last=!last; //滚动(取反即可)
    }
    printf("%d\n",f[n&1][m][k]); //输出,n&1取答案的第一维在滚动数组中是0还是1
    return 0;
}
最后修改:2019 年 09 月 23 日 10 : 27 PM

发表评论