讨论 / 跪求242的优化详解,说明要详尽
二中的废柴 2011-11-07 06:54:00
点我顶贴 收藏 删除
var

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

#1 TYF@2011-10-29 07:16:00
回复 删除
这一题考察动态规划及其优化。

很显然,每一个人偶最多只需要移动一次便可到达正确位置。但是从样例中可以看出,有一些人偶是不需要动的,那么最终的答案便是 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)。

#2 二中的废柴@2011-10-29 18:50:00
回复 删除
回复 沙发TYF 的帖子

......别抄题解啊,解释,解释LCS如何转LIS

#3 二中的废柴@2011-11-04 08:03:00
回复 删除
......

.....

#4 二中的废柴@2011-11-07 06:54:00
回复 删除
别沉了呀

#5 二中的废柴@2011-11-07 06:54:00
回复 删除
急用啊
查看更多回复
提交回复