W
h
y
D
i
d
t
h
e
C
o
w
C
r
o
s
s
t
h
e
R
o
a
d
Why\ Did\ the\ Cow\ Cross\ the\ Road
Why Did the Cow Cross the Road
题目描述见链接 .
正
解
部
分
\color{red}{正解部分}
正解部分
设
F
[
i
,
j
]
F[i, j]
F[i,j] 表示
A
A
A 序列前
i
i
i 项,
B
B
B 序列前
j
j
j 项 的最大匹配数,
i
,
j
i,j
i,j 不相连:
F
[
i
,
j
]
=
max
(
F
[
i
−
1
,
j
]
,
F
[
i
,
j
−
1
]
)
F[i, j] = \max(F[i-1,j],F[i,j-1])
F[i,j]=max(F[i−1,j],F[i,j−1])
i
,
j
i, j
i,j 相连:
F
[
i
,
j
]
=
max
(
F
[
i
−
1
,
j
−
1
]
+
1
)
F[i, j] = \max(F[i-1,j-1]+1)
F[i,j]=max(F[i−1,j−1]+1)
经典的最长公共子序列算法 .
考虑优化, 发现
i
i
i 与
j
j
j 相连当且仅当
∣
A
i
−
B
j
∣
≤
4
|A_i-B_j| \le 4
∣Ai−Bj∣≤4, 于是在
i
i
i 确定的情况下,
j
j
j 最多只有
9
9
9 个可能的取值,
所以可以记下
B
j
B_j
Bj 的位置
p
o
s
B
j
pos_{B_j}
posBj 从小到大枚举
i
i
i, 再枚举
9
9
9 种可能的
B
j
B_j
Bj, 从
F
[
i
−
1
,
0
.
.
.
p
o
s
B
j
−
1
−
1
]
+
1
F[i-1, 0 \ ...\ pos_{B_j-1}-1]+1
F[i−1,0 ... posBj−1−1]+1 转移过来, 使用 树状数组 优化 最大前缀 即可实现
O
(
9
×
N
log
N
)
O(9\times N \log N)
O(9×NlogN) .
实
现
部
分
\color{red}{实现部分}
实现部分
#include<bits/stdc++.h>
#define reg register
const int maxn
= 100005;
int N
;
int A
[maxn
];
int B
[maxn
];
int tmp
[maxn
];
int pos
[maxn
];
struct Bit_Tree
{
int v
[maxn
], lim
;
void Add(int k
, int x
){
while(k
<= lim
){
v
[k
] = std
::max(v
[k
], x
);
k
+= k
&-k
;
}
}
int Query(int k
){
if(k
<= 0) return 0;
int s
= 0;
while(k
){
s
= std
::max(s
, v
[k
]);
k
-= k
&-k
;
}
return s
;
}
} bit_t
;
int main(){
scanf("%d", &N
);
for(reg
int i
= 1; i
<= N
; i
++) scanf("%d", &A
[i
]);
for(reg
int j
= 1; j
<= N
; j
++) scanf("%d", &B
[j
]), pos
[B
[j
]] = j
;
bit_t
.lim
= N
;
for(reg
int i
= 1; i
<= N
; i
++){
int dlim
= std
::max(1, A
[i
]-4), ulim
= std
::min(N
, A
[i
]+4);
for(reg
int j
= dlim
; j
<= ulim
; j
++) tmp
[j
] = bit_t
.Query(pos
[j
]-1) + 1;
for(reg
int j
= dlim
; j
<= ulim
; j
++) bit_t
.Add(pos
[j
], tmp
[j
]);
}
printf("%d\n", bit_t
.Query(N
));
return 0;
}
