讨论 / lcs转成lis
wuqinghua068 2010-09-29 02:01:00
点我顶贴 收藏 删除
作法:

設有序列A,B。

記序列A中各個元素在B 中的位子(降序排列)

然後按在A中的位置依次列

出按後求A的最長遞增子序列

例如:有A={a,b,a,c,x},B={b,a,a,b,c,a}

則有a={6,3,2},b={4,1},c={5};x=/;(注意降序排列)

然後按A中次序排出

{a(6,3,2),b(4,1),a(6,3,2),c(5),x()}={6,3,2,4,1,6,3,2,5};

對此序列求最長遞增子序列即可~~

转自某牛Blog

查看更多回复
提交回复