luogu_P2679 子串

传送门：https://www.luogu.org/problem/P2679

这是个鬼的字符串啊，明明是dp好嘛，哼！

本人sb错误原因：

1. 数组开大了，算来算去忘记乘以longlong的8了
2. TLE，无脑三重循环，没有剪去无用状态

dp转移方程不知道为啥，感觉就是这样，然后样例过了。也就过了......

#include<cstdio>
#include<algorithm>
#include<cstring>
#define R register
using namespace std;
const int mod=1000000007;
int n,m,k,cur=1;
char a[1100],b[220];
int f[2][1100][220];
int main (){
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s",a+1);scanf("%s",b+1);
    for(R int i=0;i<=n;i++){
        f[cur^1][i][0]=1;
    }
    for(R int i=1;i<=k;i++){
        memset(f[cur],0,sizeof(f[cur]));
        for(R int j=i;j<=m;j++){
            for(R int l=j;l<=n;l++){
                if(a[l]==b[j]){
                    int now=0;
                    while(a[l-now]==b[j-now]&&now<min(j,l)){
                        (f[cur][l][j]+=f[cur^1][l-now-1][j-now-1])%=mod;
                        now++;
                    }
                }
                (f[cur][l][j]+=f[cur][l-1][j])%=mod;
            }
        }
        cur^=1;
    }
    printf("%d\n",f[cur^1][n][m]%mod);
    return 0;
}

View Code