B - Dividing Subsequence
具体题面信息见上述链接
有两个长度为 n n n 的全排列序列， P = p 1 , p 2 . . . p n P = p_1,p_2...p_n P=p1,p2...pn和 Q = q 1 , q 2 . . . q n Q = q_1,q_2...q_n Q=q1,q2...qn 。从 P , Q P,Q P,Q 中取出长度为 k k k 的子序列，使得子序列 P s u b = a 1.. k P_{sub}=a_{1..k} Psub=a1..k和 Q s u b = b 1.. k Q_{sub}=b_{1..k} Qsub=b1..k 满足任意 i i i , b i b_i bi 是 a i a_i ai 的整数倍。
题解本题需要找出两个子序列，并且满足对应位置是倍数的匹配关系。使得子序列最长的匹配思路与最长公共子序列问题比较相似。
全排列最长公共子序列问题求解的动态规划思路是：遍历匹配序列，将匹配序列的元素与模式序列中的元素进行匹配，动态规划数组
f
i
f_i
fi 的含义是以模式序列中第i项为结尾的最长公共子序列的长度。
本题与最长公共子序列问题不同的是：最长公共子序列问题匹配序列中的元素与模式序列中的元素的匹配是唯一的，本题中，这个匹配不唯一，所以我们要考虑匹配序列中的元素与模式序列中的哪一个元素匹配最佳。
我们设序列
P
P
P是匹配序列，
Q
Q
Q是模式序列。
因为
b
i
b_i
bi 是
a
i
a_i
ai 的整数倍，所以只需要对匹配序列元素
p
i
p_i
pi 的整数倍的模式序列元素
q
j
q_j
qj 进行匹配即可。 如果我们选择将
p
i
p_i
pi 和
q
j
q_j
qj 进行匹配，那么这两个元素位于子序列中的对应位置，以这两个元素为结尾的，子序列的最长长度
f
j
f_j
fj就是位于模式序列元素
j
j
j之前最长的匹配长度，对于
f
j
f_j
fj 的转移方程为
f
j
=
m
a
x
(
m
a
x
(
f
1....
(
j
−
1
)
树
状
数
组
维
护
)
,
f
j
)
f_j = max(max(f_{1....(j-1)}树状数组维护),f_j)
fj=max(max(f1....(j−1)树状数组维护),fj)
建议对于每一个匹配序列中的元素与模式序列进行匹配时，可以按照匹配序列位置从后往前进行匹配，防止动态规划的过程出现错误。
其实，本题动态规划的转移方程与全排列最长公共子序列问题基本相同，主要的区别就在于需要将
P
P
P序列对
Q
Q
Q序列的多个可能位置都进行匹配，而不是单单一个位置。
这样做时间复杂度也是满足要求的
我的代码
