Bzoj 2423(DP最长公共子序列)

BZOJ 2423
题意:给定两个长度为$n, m$字符串, 求最长公共子序列长度和方案数$\mod 10^{8}$ $n,m\leq 5000$

第一问太简单不再说,主要看第二问
对于第二问,我们当前第一问的 DP 状态是 $ dp(i, j) $ 表示第一个串匹配到 $ i $,第二个串匹配到 $ j $ 的最长公共子序列。
然后我们再加一个数组 $ g(i, j) $ 表示第一个串匹配到 $ i $,第二个串匹配到 $ j $ 的最长公共子序列方案数。
对于这个数组的转移:
当 $ a_i = b_j $ 时,方案数加上$ g(i-1,j-1) $ 如果当前的 DP 值等于 $ dp(i-1, j) $ 或 $ dp(i, j-1) $,那么加上这些方案数
否则如果当前的 DP 值等于 $ dp(i-1, j) $ 或 $ dp(i, j-1) $,那么加上这些方案数。但是如果当前还等于 $ dp(i-1, j-1) $,说明 $ a_i , b_j $ 没做贡献,说明两个 LCS 均是从$i-1,j-1$的位置转移而来,减掉$ g(i-1,j-1) $即可。

知识点:
1、看限制开数组,不要爆空间
2、方案数可以用容斥的方法来求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MO = 100000000, MAXN = 5000 + 5;
int la, lb, dp[2][MAXN], g[2][MAXN];
char a[MAXN], b[MAXN];
void clean() {
ms(dp, 0);
}
int solve() {
scanf("%s%s", a + 1, b + 1);
clean();
la = strlen(a + 1) - 1, lb = strlen(b + 1) - 1;
int cur = 0;
for (int i = 0; i <= lb; ++i) g[cur ^ 1][i] = 1;
for (int i = 1; i <= la; ++i) {
for (int j = 0; j <= lb; ++j) dp[cur][j] = 0, g[cur][j] = 0;
g[cur][0] = 1;
for (int j = 1; j <= lb; ++j) {
dp[cur][j] = max(dp[cur ^ 1][j], dp[cur][j - 1]);
if (a[i] == b[j]) {
dp[cur][j] = dp[cur ^ 1][j - 1] + 1;
g[cur][j] = g[cur ^ 1][j - 1];
if (dp[cur][j] == dp[cur ^ 1][j]) g[cur][j] = (g[cur][j] + g[cur ^ 1][j]) % MO;
if (dp[cur][j] == dp[cur][j - 1]) g[cur][j] = (g[cur][j] + g[cur][j - 1]) % MO;
} else {
if (dp[cur][j] == dp[cur ^ 1][j]) g[cur][j] = (g[cur][j] + g[cur ^ 1][j]) % MO;
if (dp[cur][j] == dp[cur][j - 1]) g[cur][j] = (g[cur][j] + g[cur][j - 1]) % MO;
if (dp[cur][j] == dp[cur ^ 1][j - 1]) g[cur][j] = (g[cur][j] - g[cur ^ 1][j - 1] + MO) % MO;
}
}
cur ^= 1;
}
printf("%d\n%d\n", dp[cur ^ 1][lb], g[cur ^ 1][lb]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
------ 本文结束 ------