[NOIP2015]子串

Luogu2679

/*
思路清晰：
1.状态
2.转移方程：哪些状态相互影响/记忆化搜索思想
3.循环顺序
4.优化

*/
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int mod=1e9+7;
const int MAXN=1005;
const int MAXM=205;

char a[MAXN],b[MAXM];
LL dp[2][MAXM][MAXM][2];
int n,m,num,ans;

int main(){
    scanf("%d%d%d",&n,&m,&num);
    scanf("%s%s",a+1,b+1);
    dp[0][0][0][0]=dp[1][0][0][0]=1;//状态最重要
    for(int i=1;i<=n;i++){
        int now=i&1;//应该先得一些分再去想优化
        for(int j=1;j<=m;j++)
        for(int k=1;k<=num;k++){//根据dp方程反推循环顺序
            dp[now][j][k][0]=(dp[now^1][j][k][0]+dp[now^1][j][k][1])%mod;
            if(a[i]==b[j])
                dp[now][j][k][1]=(dp[now^1][j-1][k-1][0]+dp[now^1][j-1][k-1][1]+dp[now^1][j-1][k][1])%mod;
                //                    单独成串，不相连      单独成串，相连          接上一个串
            else
                dp[now][j][k][1]=0;
        }
    }
    printf("%lld\n",(dp[n&1][m][num][0]+dp[n&1][m][num][1])%mod);
}