题解 P2679 【子串】

· · 题解

透彻是多么重要

今天考试推了半天的方程 没有推出来 （∏_∏）

蒟蒻已无语 dalao狂鄙视

------------------------------------吐槽时间----------------------------------------

首先 这道题看上去是一道字符串匹配题 AC自动机orKMP

可是 再多看看题面 不是

我们想到了什么 DP

考虑当前匹配成功与匹配不成功

分别用

ans[i][j][k] 记录当前 A[i]不论等不等于B[j] 我们可以选用也可以不选用 使用k个子串方案数

res[i][j][k] 记录当前 A[i]==B[j] 并且我们选用A[i]和B[j] 方案数 使用k个子串方案数

得到状态转移方程

if(A[i]==B[j])
  res[i][j][k]=(ans[i-1][j-1][k-1]+res[i-1][j-1][k])%mod;
//ans[i-1][j-1][k-1] 我们把当前匹配字符单独算做一个子串
//res[i-1][j-1][k] 我们把当前匹配字符与上面的和为一个子串

else res[i][j][k]=0;
//不成则为零

ans[i][j][k]=(res[i][j][k]+ans[i-1][j][k])%mod;
//res[i][j][k] 使用当前字符
//ans[i-1][j][k] 不使用当前字符

貌似一切大吉了？？

可是 ans[1000][20][20]

保底都开不下 更何况还要开大以防止RE

考虑滚动数组

if(A[i] == B[j]) 
res[now][j][p]=(res[now^1][j-1][p]+ans[now^1][j-1][p-1])%mod;
else res[now][j][p]=0; 
ans[now][j][p]=(ans[now^1][j][p]+res[now][j][p])%mod;

因为状态转移时 只需调用 i and i-1

所以只需在1和0之间滚动即可

dalao勿喷

CODE：

#pragma GCC optimize(3)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>
#define ll long long
#define inf 0x7fffffff
#define mod 1000000007
#define N 500008
#define IL inline
#define M 1008611
#define D double
#define ull unsigned long long
#define R register
using namespace std;
template<typename T>void read(T &a)
{
    T x=0,f=1;char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=0;ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
    }
    a=f?x:-x;
}
/*-------------OI使我快乐-------------*/
int n,m,k,now;
int ans[3][1010][1010],res[3][1010][1010];
char A[1010],B[1010]; 
int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    read(n);read(m);read(k);
    scanf("%s%s",A+1,B+1);
    ans[0][0][0]=1;now=1;
    for(R int i=1;i<=n;++i){
        ans[now][0][0]=1;
        for(R int j=1;j<=m;++j)
         for(R int p=1;p<=k;++p){
            if(A[i] == B[j]) res[now][j][p]=(res[now^1][j-1][p]+ans[now^1][j-1][p-1])%mod;
            else res[now][j][p]=0; 
            ans[now][j][p]=(ans[now^1][j][p]+res[now][j][p])%mod;
         }
        now^=1;      
    }
    printf("%d\n",ans[now^1][m][k]);
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

NOIP 2018 即将到来

不透彻的赶紧透彻 没准会RP++