Codeforces 682D Alyona and Strings

链接

传送门

题意

给出两个字符串$s$、$t$和整数$k$,在$s$、$t$中找出出现顺序相同的$k$段相同连续子串,输出$k$段子串最大长度和。

思路

与最长公共子序列类似,定义状态$dp[i][j][k][l]$表示$s$匹配到了第$i$个字符、$t$匹配到了第$j$个字符,当前已经匹配了$k$段子串,$l$为0时代表最后一段子串停止匹配、为1时代表最后一段子串还在匹配。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1005;
int dp[maxn][maxn][11][2];
char s[maxn], t[maxn];
int main() {
int n, m, K;
scanf("%d%d%d", &n, &m, &K);
scanf("%s%s", s + 1, t + 1);
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int k = 1; k <= K; ++k) {
if (s[i] == t[j]) {
dp[i][j][k][1] = max(dp[i - 1][j - 1][k][1], dp[i - 1][j - 1][k - 1][0]) + 1;
}
dp[i][j][k][0] = max(dp[i][j][k][1], max(dp[i - 1][j][k][0], dp[i][j - 1][k][0]));
}
ans = max(ans, dp[i][j][K][0]);
}
}
printf("%d\n", ans);
return 0;
}

支付宝扫码领红包