目录

  1. 引言
  2. BZOJ 4275: [ONTAK2015]Badania naukowe
    1. Description
    2. Input
    3. Output
    4. Sample Input
    5. Sample Output
    6. HINT
    7. 题目分析
    8. 代码

引言

BZOJ 4275: [ONTAK2015]Badania naukowe 题解

BZOJ 4275: [ONTAK2015]Badania naukowe

  • Time Limit: 3 Sec

  • Memory Limit: 256 MB

Description

给定三个数字串A,B,C,请找到一个A,B的最长公共子序列,满足C是该子序列的子串。

Input

第一行包含一个正整数n(1<=n<=3000),表示A串的长度。
第二行包含n个正整数,其中第i个数表示Ai
第三行包含一个正整数m(1<=m<=3000),表示B串的长度。
第四行包含m个正整数,其中第i个数表示Bi
第五行包含一个整数k(0<=k<=3000),表示C串的长度。
第六行包含k个正整数,其中第i个数表示Ci

Output

输出一个整数,即满足条件的最长公共子序列的长度,如果无解输出-1。特别的,如果k为0且无解,请输出0。

Sample Input

7

1 2 2 3 1 1 2

6

1 2 1 3 1 2

2

3 2

Sample Output

4

HINT

找到的最长个公共子序列为(1,2,3,2)。

题目分析

就是一道ZZ的LCS上DP,一开始我还以为需要KMP……

后来发现直接暴力枚举开头,然后贪心匹配,一旦匹配结束就退出并记录这个区间,然后DP一下前后缀LCS,再枚举两个串分别的匹配位置,更新一下答案就好……

代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#define maxn 4005
#define pii pair<int, int>
#define fi first
#define se second
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
#define gc() ((p1 == p2 && (p2 = (p1 = buffer) + fread(buffer, 1, maxn, stdin), p1 == p2)) ? EOF : *p1++)
using namespace std;
char *p1, *p2;
char buffer[maxn];
template <class T> void read(T& x){
char ch = gc(); x = 0; bool f = 1;
while (!('0' <= ch && ch <= '9') && ch != '-') ch = gc();
if (ch == '-') ch = gc(), f = 0;
while ('0' <= ch && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = gc();
if (!f) x = -x;
}
int n, m, k;
int a[maxn];
int b[maxn];
int c[maxn];
int ca = 0;
pii sa[maxn];
int cb = 0;
pii sb[maxn];
int pre[maxn][maxn];
int suf[maxn][maxn];
void init(){
rep(i, 1, n) {
if (a[i] != c[1]) continue;
pii op = pii(i, 0);
int now = 2;
bool f = 0;
rep(j, i + 1, n){
if (now > k) {
op.se = j - 1;
sa[++ca] = op;
f = 1;
break;
}
if (a[j] == c[now]) now++;
}
if (!f && now > k) {
op.se = n;
sa[++ca] = op;
f = 1;
}
if (!f) break;
}
rep(i, 1, m) {
if (b[i] != c[1]) continue;
pii op = pii(i, 0);
int now = 2;
bool f = 0;
rep(j, i + 1, m){
if (now > k) {
op.se = j - 1;
sb[++cb] = op;
f = 1;
break;
}
if (b[j] == c[now]) now++;
}
if (!f && now > k) {
op.se = m;
sb[++cb] = op;
f = 1;
}
if (!f) break;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("bad.in", "r", stdin);
#endif
read(n);
rep(i, 1, n) read(a[i]);
read(m);
rep(i, 1, m) read(b[i]);
read(k);
rep(i, 1, k) read(c[i]);
rep(i, 1, n) rep(j, 1, m) pre[i][j] = (a[i] == b[j]) ? (pre[i - 1][j - 1] + 1) : max(pre[i - 1][j], pre[i][j - 1]);
per(i, n, 1) per(j, m, 1) suf[i][j] = (a[i] == b[j]) ? (suf[i + 1][j + 1] + 1) : max(suf[i + 1][j], suf[i][j + 1]);
if (!k){
printf("%d", pre[n][m]);
return 0;
}
init();
int ans = -1;
rep(i, 1, ca) rep(j, 1, cb) ans = max(ans, pre[sa[i].fi - 1][sb[j].fi - 1] + k + suf[sa[i].se + 1][sb[j].se + 1]);
printf("%d", ans);
return 0;
}