题解【洛谷P2679】[NOIP2015]子串

题面

看到求方案数,还要对 \(1000000007\ (1e9+7)\) 取模,一般这样的问题都要考虑 动态规划

我们设 \(dp_{i,j,k,0/1}\) 表示 \(A_{1\dots i}\) 中选取 \(k\) 个子串,与 \(B_{1\dots j}\) 匹配,且 \(A_{i}\) 选 / 不选的方案数。

分情况讨论转移:

  • 若 \(A_i = B_j\),
    • \(dp_{i,j,k,0} = dp_{i-1,j,k,0}+dp_{i-1,j,k,1}\)。
      • 不选 \(A_i\) 就说明 \(A_{1\dots i - 1}\) 已经与 \(B_{1\dots j}\) 匹配上了,那么方案数就是 \(A_{i-1}\) 选 / 不选的方案数之和;
    • \(dp_{i,j,k,1}=dp_{i-1,j-1,k,1}+dp_{i-1,j-1,k-1,0}+dp_{i-1,j-1,k-1,1}\)。
      • 第一种情况,将 \(A_i\) 接到 \(A_{i-1}\) 的后面,且 \(A_{i-1}\) 在第 \(k\) 个子串,必须选择 \(A_{i-1}\),直接加上方案数。
      • 第二种情况,如果不选择 \(A_{i-1}\),那么 \(A_i\) 就必须作为第 \(k\) 个子串,\(A_{i-1}\) 前面的子串只能有 \(k-1\) 个。
      • 第三种情况,选择 \(A_{i-1}\),并且新开一个长度为 \(1\) 的子串 \(A_i\)。
  • 若 \(A_i \neq B_j\),
    • \(dp_{i,j,k,0}=dp_{i-1,j,k,0}+dp_{i-1,j,k,1}\)。
      • 不选择 \(A_i\) 的方案数就是 \(A_{1\dots i-1}\) 已经和 \(B_{1\dots j}\) 匹配上的方案数,实质上就是 \(A_{i-1}\) 选 / 不选的方案数。其实和 \(A_i=B_j\) 的情况是一样的。
    • \(dp_{i,j,k,1} = 0\)。
      • 如果要选择 \(A_i\),且 \(A_{1\dots i}\) 与 \(B_{1\dots j}\) 匹配上,那么没有一种方案符合这种要求,方案数为 \(0\)。

讨论有些复杂,可以自己在纸上再推一遍。

然而这样做空间会爆炸。

我们发现每一次转移 \(i\) 时的状态只与 \(i-1\) 的状态有关,于是我们可以开一个滚动数组把这一维的空间优化成 \(2\)。开滚动数组只需要将第一维全部 & 1 即可。

边界初始化 \(dp_{0,0,0,0}=dp_{1,0,0,0}=1\),因为选 \(0\) 个子串时任何的 \(A_{1\dots i}\) 都可以与空串匹配,因为此时什么都不要取。

这样做我们就可以通过本题了。

注意开 \(\text{long long}\)。

#include <bits/stdc++.h>

using namespace std;

const int mod = 1000000007;

int n, m, K;
long long dp[2][203][203][2]; //注意开 long long
char a[1003], b[203]; int main()
{
cin >> n >> m >> K;
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+=1)
for (int j = 1; j <= m; j+=1)
for (int k = 1; k <= K; k+=1) //转移
if (a[i] == b[j])
dp[i & 1][j][k][1] = (dp[(i - 1) & 1][j - 1][k][1] + dp[(i - 1) & 1][j - 1][k - 1][0] + dp[(i - 1) & 1][j - 1][k - 1][1]) % mod,
dp[i & 1][j][k][0] = (dp[(i - 1) & 1][j][k][0] + dp[(i - 1) & 1][j][k][1]) % mod;
else
dp[i & 1][j][k][1] = 0,
dp[i & 1][j][k][0] = (dp[(i - 1) & 1][j][k][1] + dp[(i - 1) & 1][j][k][0]) % mod;
cout << (dp[n & 1][m][K][0] + dp[n & 1][m][K][1]) % mod << endl; //输出最后答案
return 0;
}
上一篇:洛谷P2679 子串


下一篇:设计模式之迭代器模式(Iterator Pattern)