a,b:array[1..10000]of longint;
f:array[0..10000,0..10000]of longint;
i,j,k,n,m:longint;
begin
readln(n);
for i:=1 to n do read(a[i]);readln;
for i:=1 to n do read(b[i]);
for i:=1 to n do
for j:=1 to n do
if a[i]=b[j] then f[i,j]:=f[i-1,j-1]+1 else
if f[i-1,j]>f[i,j-1] then f[i,j]:=f[i-1,j] else f[i,j]:=f[i,j-1];
writeln(n-f[n,n]);
end.
本人LCS
很显然,每一个人偶最多只需要移动一次便可到达正确位置。但是从样例中可以看出,有一些人偶是不需要动的,那么最终的答案便是 n 减去不需要移动的人偶数。
我们需要让不需要移动的人偶数尽可能大,那么它最大能到多大呢?相信大家已经看出来了,它的最大值便是两个序列的最长公共子序列(LCS)的长度。这样,我们成功地把这个问题转换为 LCS 问题。
LCS 的经典方程大家都知道:
设两个序列为 a、b,用 f[i, j] 表示第一个序列的前 i 个数,和第二个序列的前 j 个数的最长公共子序列的长度。
若 a[i] = b[j],则
f[i, j] = max{f[i - 1, j - 1] + 1, f[i, j - 1], f[i - 1, j]}
若 a[i] <> b[j],则
f[i, j] = max{f[i, j - 1], f[i - 1, j]}
边界条件:
f[0, j] = 0
f[i, 0] = 0
但是这样的算法是 O(n^2) 的,对于高达 100000 的 n,无论是时间还是空间都无法满足要求,虽然可以采用滚动数组解决空间问题,但是时间问题还是不能解决。
众所周知一般 LCS 问题的最优的时间复杂度即为 O(n^2),那还有什么可以优化的余地呢?这时,我们要利用数据的稀疏性来进行优化。
观察上面的方程,我们发现,只有当 a[i] = b[j] 的时候 f 的值才会增加。而原数据是 n 的两个排列,因而只有 n 个相等点!
抓住这一点我们就可以优化动态规划方程。我们设在第一个序列中与 a[i] 相等的 b[j] 点的下标为 pair[i],那么有:
f[i, pair[i]] = max{f[j, pair[j]} (j <= i, pair[j] < pair[i])
这样,我们只需要保存出长度为 i 的公共子序列的最小下标 j,再用二分查找维护即可。
空间复杂度 O(n),时间复杂度 O(nlgn)。