子串

· · 题解

  1. 状态量　

考虑这道题中的变量：a串长度， b串长度，k段。

所以我们初步可以设一个三维的状态量f[i][j][k];

表示a[1 \sim i]到b[1 \sim j]用k段匹配。

然后进一步考虑， 发现这个状态量的转移方程不好推。

其原因是当使用a[j]与不使用a[j]时状态混淆，所以这个状态量一定有问题。

所以我们加一维，进行区别。

最终状态量：f[i][j][k][0 / 1], 0即是不使用，反之亦然。

  1. 方程
f[i][j][k][0] = f[i - 1][j][k][1] + f[i - 1][j][k][0]

若a[i] = b[j], 则

f[i][j][k][1] = f[i - 1][j - 1][k - 1][1] + f[i - 1][j - 1][k][1] + f[i][j - 1][k - 1][0]

逻辑在于：

当前字符不使用时，可以从两个方向转移而来：

上个字符的使用、不使用皆可。

当前字符使用时，可以从三个方向转移而来：

[注]显然当这两个字符相等时，b串的当前字符是不能用的。

(1)上阶段有k段，而当前要接上，则上个字符必然使用。

(2)上阶段有k - 1段，则当前使不使用皆可。

  1. 边界

易知,f[i][1][1][0] = \sum_{j = 1}^{i - 1}(a[j] == b[1])

划重点！！

这可能是博主在做这道题的时候最懵的一点了，不过手玩按逻辑推一下也是过得来的。看懂了这一点，就搞懂了程序。所以仅作提示：注意状态量的定义。

接下来是最激动人心的时刻：


/************************************************
*Author        :  Jack
*Created Time  :  2019.10.25.21:17
*Mail          :  [email protected]
*Problem       :  P2679
*Extra         :  [NOIP2015] D2T2 
************************************************/
#include <bits/stdc++.h>
#define int long long
using namespace std;
//dp[i][j][k][1] a[i] & b[j] for k 
const int maxn = 1e3 + 2;
const int maxk = 2e2 + 2;
const int MOD = 1e9 + 7;
int f[2][maxk][maxk][2];
int n, m, NOW, PRE, s, t;
char a[maxn], b[maxn];
signed main() {
//    freopen("P2679.in","r",stdin);
//    freopen("P2679.out","w",stdout);
    scanf("%lld%lld%lld", &n, &m, &t);
    scanf("%s%s", a + 1, b + 1);
    NOW = 0, PRE = 1;
    for(int i = 1;i <= n;i ++){
        swap(NOW, PRE);
        f[NOW][1][1][0] = s;
        if(a[i] == b[1]){
            f[NOW][1][1][1] = 1;
            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] + f[PRE][j - 1][k - 1][0];
                    f[NOW][j][k][1] %= MOD;
                }
                f[NOW][j][k][0] = f[PRE][j][k][0] + f[PRE][j][k][1];
                f[NOW][j][k][0] %= MOD;
            }
        }
        for(int j = 1;j <= m;j ++){
            for(int k = 1;k <= t;k ++){
                f[PRE][j][k][0] = f[PRE][j][k][1] = 0;
            }
        }
    }
    printf("%lld", (f[NOW][m][t][1] + f[NOW][m][t][0]) % MOD);
    return 0;
}

最后，鸣谢@CRyan大佬的题解，给了我很大的启发。