「BZOJ1264」[AHOI2006]基因匹配Match

Description

卡卡昨天晚上做梦梦见他和可可来到了另外一个星球,这个星球上生物的DNA序列由无数种碱基排列而成(地球上只有44种),而更奇怪的是,组成DNA序列的每一种碱基在该序列中正好出现55次!这样如果一个DNA序列有NN种不同的碱基构成,那么它的长度一定是5N5N

卡卡醒来后向可可叙述了这个奇怪的梦,而可可这些日子正在研究生物信息学中的基因匹配问题,于是他决定为这个奇怪星球上的生物写一个简单的DNA匹配程序。

为了描述基因匹配的原理,我们需要先定义子序列的概念:若从一个DNA序列(字符串)s中任意抽取一些碱基(字符),将它们仍按在ss中的顺序排列成一个新串uu,则称uuss的一个子序列。对于两个DNA序列s1s_1s2s_2,如果存在一个序列u同时成为s1s_1s2s_2的子序列,则称u是s1s_1s2s_2的公共子序列。

卡卡已知两个DNA序列s1s_1s2s_2,求s1s_1s2s_2的最大匹配就是指s1s_1s2s_2最长公共子序列的长度。

[任务] 编写一个程序:

  • 从输入文件中读入两个等长的DNA序列;
  • 计算它们的最大匹配;
  • 向输出文件打印你得到的结果。

Input

输入文件中第一行有一个整数NN,表示这个星球上某种生物使用了NN种不同的碱基,以后将它们编号为1…N的整数。

以下还有两行,每行描述一个DNA序列: 包含5N5N1N1\cdots N的整数,且每一个整数在对应的序列中正好出现55次。

Output

输出文件中只有一个整数,即两个DNA序列的最大匹配数目。

Sample Input

1
2
3
2
1 1 2 2 1 1 2 1 2 2
1 2 2 2 1 1 2 2 1 1

Sample Output

1
7

HINT

60%60\%的测试数据中:1N10001\leq N \leq 1 000
100%100\%的测试数据中:1N200001\leq N \leq 20 000

Solution

树状数组。
LCSLCS问题转换:把Ai=BjA_i=B_j的数对(i,j)(i,j)当作平面上的点,选出尽可能多的点,使得对于任意一个在序列点iixi>xi1x_i>x_{i-1}yi>yi1y_i>y_{i-1}。(转自GXZlegend)
fif_{i}表示到第ii个点位置的最大子序列长度
fi=max{fj+1}(yj<yi,xj<xi)f_{i}=\max\{f_j+1\}(y_j<y_i,x_j<x_i)
先把点按照yy排序,然后用树状数组维护[1,xi1][1,x_i-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
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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 21000*25;
int n;
int a[N],b[N];
int val[2][N][6];
int c1[N], c2[N];
struct T {
int x, y;
}t[N * 25];
int tot;
bool cmp(T _x, T _y) {
return _x.y < _y.y;
}
int g[N];
void add(int x, int v) {
for(; x <= n*5; x += x & -x) g[x] = max(g[x], v);
}
int query(int x) {
int res = 0;
for(; x; x -= x & -x) res = max(res, g[x]);
return res;
}
int f[N];
int main() {
n = read();
for(int i = 1; i <= n * 5; ++i) a[i] = read(), val[0][a[i]][++c1[a[i]]] = i;
for(int i = 1; i <= n * 5; ++i) b[i] = read(), val[1][b[i]][++c2[b[i]]] = i;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= 5; ++j)
for(int k = 1; k <= 5; ++k)
t[++tot] = (T){val[0][i][j], val[1][i][k]};
sort(t + 1,t +1 +tot, cmp);
int ans = 0;
for(int i = 1, j; i <= tot; i = j) {
j = i;
while(t[i].y == t[j].y) ++j;
for(int k = i; k < j; ++k) f[k] = query(t[k].x - 1) + 1;
for(int k = i; k < j; ++k) add(t[k].x, f[k]);
}
for(int i = 1; i <= tot; ++i) {
// printf("%d:(%d,%d) %d\n", i, t[i].x, t[i].y, f[i]);
ans = max(ans, f[i]);
}
writeln(ans);
return 0;
}