P2679 [NOIP 2015 提高组] 子串

题目

P2679 [NOIP 2015 提高组] 子串

算法标签: 动态规划, 线性$dp$

思路

因为涉及到两个字符串, 因此最少需要两维状态$i,j$, 然后还要统计当前已经使用了多少个$A$当中的子串$k$, 对于当前位置$A[i]$和$B[j]$是否相等也是一种决策, 因此可以设计状态表示$f[i][j][k][l]$, 表示考虑$A$的前$i$个字符, $B$的前$j$个字符, 已经使用了$k$个子串, 并且当前位置$i$的字符选择或者不选择的状态是$l$的所有方案的方案数量, 计算空间$1000\times 1000\times 200\times 2\times 4byte$大约是$381MB$, 空间会超过题目限制, 观察到状态转移只与上一个$i$有关, 可以使用滚动数组进行空间优化

如何进行状态转移?
对于当前位置$A[i]$如果与$B[j]$相等, 那么可以选择将当前字符作为子串的延续或者新的子串的开始, 如果不相等那么不能选择当前字符

代码

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 1010, M = 210, MOD = 1e9 + 7;int n, m, k;
int f[2][N][M][2];
string s1, s2;int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m >> k;cin >> s1 >> s2;s1 = ' ' + s1;s2 = ' ' + s2;memset(f, 0, sizeof(f));f[0][0][0][0] = 1;for (int i = 1; i <= n; ++i) {//注意这个位置, 每次滚动数组都需要将当前层的状态清空, 同时初始化f[i & 1][0][0][0]空字符串匹配也是一种方案memset(f[i & 1], 0, sizeof(f[i & 1]));f[i & 1][0][0][0] = 1;for (int j = 1; j <= m; ++j) {for (int l = 1; l <= k; ++l) {f[i & 1][j][l][0] = (f[i - 1 & 1][j][l][0] + f[i - 1 & 1][j][l][1]) % MOD;if (s1[i] == s2[j]) {f[i & 1][j][l][1] = f[i - 1 & 1][j - 1][l][1];f[i & 1][j][l][1] = (f[i & 1][j][l][1] + (f[i - 1 & 1][j - 1][l - 1][0] + f[i - 1 & 1][j - 1][l - 1][1]) % MOD) % MOD;}else {f[i & 1][j][l][1] = 0;}}}}int ans = (f[n & 1][m][k][0] + f[n & 1][m][k][1]) % MOD;cout << ans << "\n";return 0;
}

*警示后人

在考虑状态转移的时候要考虑清楚初始状态是否是正确的