题意:有两个长度分别为p+1和q+1的序列,每个序列中的元素互不相同,且都是1到n^2之间的整数(2<=n<=250),两个序列的第一个元素均为1。求A和B的最长公共子序列的长度。
思路:原本是LCS问题,但是普通的LCS算法复杂度是O(pq)显然TLE。注意到元素均不相同,可以把A中的元素重新编号为1到p+1。例如样例中的A={1,7,5,4,8,3,9},B={1,4,3,5,6,2,8,9},那么把A重新编号为{1,2,3,4,5,6,7},则B={1,4,6,3,0,0,5,7},其中0表示A中没有出现过(事实上可以直接删除这些元素,因为他们肯定不在LCS里面)。这时候,答案就是新的B的LIS......
阅读全文