P2679 子串
题意:
给出两个仅含小写字母的字符串 \(A\) 和 \(B\) 要求从 \(A\) 中取出 \(k\) 个互不重叠的非空子串,然后把这 \(k\) 个子串按照其在字符串 \(A\) 中的顺序依次连接起来形成新的字符串。
求有多少种方案可以使得这个新字符串和字符串 \(B\) 相等?
思路:
定义 \(f[i][j][k]\) ,为遍历到第 \(i\) 个字符,取出了 \(k\) 个子串,这 \(k\) 个子串,匹配到 \(B\) 字符串的第 \(j\) 个字符,划分为匹配的时候当前是成为一个新的子串,还是和之前的合并。但是合并的时候,必须先前面也是匹配的,所以考虑再加一个维度,标记第 \(i\) 个点是否选入。定义 \(f[i][j][k][h]\) :为遍历到 \(A\) 串的第 \(i\) 个位置使用了 \(k\) 个子串匹配了 \(B\) 的前 \(j\) 个字符,第 \(i\) 个位置选或不选的方案数。
划分依据为 第 \(i\) 个选或者不选
- 当 \(a_i = b_j\) 时
- 当前不选:\(f_{i,j,k,0} = f_{i - 1,j,k,0} + f_{i - 1,j,k,1}\)
- 当前选:\(f_{i,j,k,1} = f_{i - 1,j - 1,k - 1,0} + f_{i - 1,j - 1,k - 1,1}\)
- 当 \(a_i \not = b_j\) 时
- 不选情况同上
- 没办法选,\(f_{i,j,k,1} = 0\)
发现空间太大了,然后观察公式,发现只需要用到 \(i - 1\) 所以可以滚动,注意这里因为更新 \(k\) 时会用到 \(i -1\) 的 \(k\) 所以不能自我滚动。
实现:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 5, M = 205, mod = 1e9 + 7;
char a[N], b[M];
ll f[2][M][M][2];
int main()
{
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
scanf("%s", a + 1);
scanf("%s", b + 1);
f[1][0][0][0] = f[0][0][0][0] = 1;
// 遍历到 a 的哪个位置
for (int i = 1; i <= n; i++)
{ // 匹配到 b 的哪个位置
for (int j = 1; j <= m; j++)
// 分成了几个子串
for (int h = 1; h <= k; h++)
{
// 当前不匹配
f[i & 1][j][h][0] = (f[(i & 1) ^ 1][j][h][0] + f[(i & 1) ^ 1][j][h][1]) % mod;
// 当前匹配
if (a[i] == b[j])
{
// 另为一段
f[i & 1][j][h][1] = (f[(i & 1) ^ 1][j - 1][h - 1][0] + f[(i & 1) ^ 1][j - 1][h - 1][1]) % mod;
// 和之前的合并为一段
f[i & 1][j][h][1] = (f[i & 1][j][h][1] + f[(i & 1) ^ 1][j - 1][h][1]) % mod;
}
else
f[i & 1][j][h][1] = 0;
}
}
printf("%lld\n", (f[n & 1][m][k][1] + f[n & 1][m][k][0]) % mod);
return 0;
}
标签:子串,int,P2679,scanf,不选,字符串
From: https://www.cnblogs.com/zxr000/p/17004204.html