题解 P2679 【子串】

· · 题解

这个奇怪的DP，那年我只得了20分我也是醉了

一个非常绕的dp，参考了一部分别人的解法理解了，觉得更好理解一些，分享给大家。

版权大概归属于codevs 34504和东营胜利一中的GaoTY哥哥，据说他也在洛谷~

希望管理员不要爆破，wiki的目的我想根本在于分享和促进大家更好地写代码，贡献分啥的不要也罢。

思路

初始的想法是设置f[i][j][k]表示A串前i个字符里，使用了k个子串，来匹配了B串前j个字符。

所以可列出最基本的方程f[i][j][k]=f[i-1][j-1][k-1]+f[i-1][j-1][k]，翻译过来就是

A串前i个字符里，使用了k个子串，匹配了B串前j个字符的方案数，等价于 单独使用第i-1个字符作为一个子串的方案数和不单独使用的方案数（包括不使用和和前面连在一起）

但正如括号里所说，这个递归方程未能解决不使用和和前面连在一起的问题，所以我们要添加一维0/1维，来表示使用了当前字符和没使用当前的字符。

所以动态转移方程变成了两个

这样转移方程就出来了。

我们再来思考边界条件。边界条件两种情况。

综上转移方程

- **f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1]**
- **（a[i]==b[j]）f[i][j][k][1]=f[i-1][j-1][k-1][0]+f[i-1][j-1][k][1]+f[i-1][j-1][k-1][1]**
- **f[i][1][1][0]=sum(a[1~i-1]==b[1])**
- **（a[i]==b[1]）f[i][1][1][1]=1 **

细节

空间复杂度

这个题如果开1000*200*200*2的话，掐指一算可得你需要大约300MB空间……

但不难发现，方程里只有i和i-1被来回调用，其余例如i-2，i-3在接下来的动态规划里都废了，所以那些空间是不需要的，我们可以把数组滚动起来。

我们开一个f[2][201][201][2]（p党请自行设置为0~x）

使用一个now和一个pre变量，__谁为1谁为0无所谓__，只要改变i就交换就可以了。

这样空间量缩小至1/50，6MB就够了。

清空滚动数组

我开始写到这里时，怎么想都觉得应该过了，但样例都挖。

后来仔细一想，明白了，滚动数组的时候，可能存在本应该f[i][1][1][1]=0的位置，变为了1（看下面的代码你就明白了），但这个位置可能无法被接下来的动规覆盖掉，因为这个位置根据方程，仅当a[i]==b[1]时才会更新，而且更新的值始终为1，变不回0。

所以，在一遍动规完成之后，必须要把f[pre]清0。

取模

加法模运算小学生难度，但是……本傻瓜写到最后了忘了写模第一遍溢出了！只得了50分……

复杂度

空间复杂度O（mk)

时间复杂度O（nmk）

好吧，4*10^8，勉强能过，最后一个点600ms，也不算差。

代码

#include<cstdio>
#include<iostream>
#define prime 1000000007
using namespace std;
char a[1001],b[201];
int n,m,t,f[2][201][201][2],s,now,pre=1;//s是用来记录之前有多少个A串字符能和B串第一个字符匹配
int main(){
    scanf("%d%d%d",&n,&m,&t);
    scanf("%s%s",a+1,b+1);//吐槽：这个奇葩的读入我以前一直没用过...
    for (int i=1;i<=n;i++){
        swap(now,pre); //交换，只要i改变
        f[now][1][1][0]=s;//边界1
        if (a[i]==b[1]) f[now][1][1][1]=1,s++;//边界2，解决了s统计的问题
        for (int j=2;j<=m;j++){
            for (int k=1;k<=t;k++){
                if (a[i]==b[j]){
                    f[now][j][k][1]=((f[pre][j-1][k-1][1]+f[pre][j-1][k][1])%prime+f[pre][j-1][k-1][0])%prime;
                }//方程2
                f[now][j][k][0]=(f[pre][j][k][0]+f[pre][j][k][1])%prime;//方程1
            }
        }
    for(int j=1;j<=m;j++)
          for(int k=1;k<=t;k++)
            f[pre][j][k][1]=f[pre][j][k][0]=0;//清空
    }
    printf("%d",(f[now][m][t][1]+f[now][m][t][0])%prime);
    return 0; 
}