编号 题目名称 状态 分数 总时间 内存 代码 提交者 提交时间
#143 #7. 切割字符串 Accepted 100 513 ms 86984 K C++ / 954 B Sengxian 2016-11-14 14:22:52
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

const int MAX_N = 1000 + 3, MAX_M = 1000 + 3, MAX_K = 10 + 1, INF = 0x3f3f3f3f;
int f[MAX_K][MAX_N][MAX_M], g[MAX_K][MAX_N][MAX_M];
char s[MAX_N], t[MAX_M];
int n, m, K;

int main() {
	freopen("string.in", "r", stdin);
	freopen("string.out", "w", stdout);
	scanf("%d%d%d%s%s", &n, &m, &K, s + 1, t + 1);
	
	memset(f, -INF, sizeof f);
	memset(g, -INF, sizeof g);
	memset(f[0], 0, sizeof f[0]);
	
	for (int k = 1; k <= K; ++k)
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j) {
				f[k][i][j] = max(f[k][i - 1][j], f[k][i][j - 1]);
				if (s[i] == t[j]) {
					f[k][i][j] = max(f[k][i][j], f[k - 1][i - 1][j - 1] + 1);
					f[k][i][j] = max(f[k][i][j], g[k][i - 1][j - 1] + 1);
					g[k][i][j] = max(f[k - 1][i - 1][j - 1] + 1, g[k][i - 1][j - 1] + 1);
				} else g[k][i][j] = -INF;
			}

	printf("%d\n", f[K][n][m]);
	return 0;
}
测试点 #1
Accepted
得分:100
用时:36 ms
内存:86984 KiB

输入文件

20 20 1
bbabaababbabbababaab
ababaaaaaaaabaaaaaba
期望输出
6
你的输出
6

测试点 #2
Accepted
得分:100
用时:40 ms
内存:86984 KiB

输入文件

20 20 1
aaaaabbabaaaaababaaa
baaaaabbaabbaaabaaaa
期望输出
8
你的输出
8

测试点 #3
Accepted
得分:100
用时:46 ms
内存:86984 KiB

输入文件

20 20 1
aabbbbbababbaabbbbab
aaabaabbababaaabbbba
期望输出
7
你的输出
7

测试点 #4
Accepted
得分:100
用时:38 ms
内存:86984 KiB

输入文件

20 20 2
abaabaaabbaabaaabaaa
abaaaabbbabbabbaaaaa
期望输出
9
你的输出
9

测试点 #5
Accepted
得分:100
用时:34 ms
内存:86980 KiB

输入文件

20 20 2
aabbabaabbbbbbbbbbba
babbbabbbabbabbbaaba
期望输出
8
你的输出
8

测试点 #6
Accepted
得分:100
用时:34 ms
内存:86980 KiB

输入文件

20 20 2
abbabaabbababbbbbbab
babbabbababaaaaababb
期望输出
11
你的输出
11

测试点 #7
Accepted
得分:100
用时:35 ms
内存:86984 KiB

输入文件

20 20 2
cbcbcabaaabccccbbabc
abbabababccaaaccaaab
期望输出
7
你的输出
7

测试点 #8
Accepted
得分:100
用时:35 ms
内存:86980 KiB

输入文件

20 20 2
cababaadcbbccdddadca
cbbabdddcabdccaaddbb
期望输出
6
你的输出
6

测试点 #9
Accepted
得分:100
用时:114 ms
内存:86984 KiB

输入文件

1000 1000 10
babbbabaabaabbbaaabbaababaabaabbbbbabbababbabaaaabaabaaabaabaababbabaabbbbbbbaaaaaaaaababbabbaabbbbabbabbba...
期望输出
141
你的输出
141

测试点 #10
Accepted
得分:100
用时:101 ms
内存:86980 KiB

输入文件

1000 1000 10
aabbaaababbabaaababbaaaabaaaabbbbaaaabbabaababbaaabbbabbbaaaabbbbbbbbabaabbaabbbbbbaabbababaaababbaabbbaaaa...
期望输出
143
你的输出
143