关于一类LIS转LCS的问题
标签： 总结 动态规划 序列DP
1.序
LIS：最长上升子序列，众所周知有n^2的算法，不过由于效率较低所以现在一般都是nlogn的算法（单调栈，树状数组解决），具体方法在此就不过多叙述。
LCS：最长公共子序列，即求两个序列的最长的相同子序列。现在所知解决这一类问题的方法只有n^2的动态规划。
而今天在这里讨论的便是一类特殊的LCS问题，通过一些转换可变成nlogn的LIS问题。
2.引入
我们可以先想一想LIS与LCS如何联系起来。LIS一般就是单个元素的问题，而LCS是涉及二元组（两个元素相同嘛）的问题。
先来思考这样一个问题，给你一串二元组（x,y），要你选取二元组序列使得x,y分别递增，问长度最大。
eg:（1,2）,（3,4）,（5,6）便是一个合法的递增二元组
如何解决呢？
其实我们只需要对x排序以后，对y按照LIS的方法解决就可以了对吧。因为对x排序以后我们就保证x是递增的了，于是接下来只需满足y递增就行了。
3.转换
现在思考LCS，我们最长公共子序列子序列也可以看成一些二元组（i1,j1）,（i2,j2）…..（in,jn）
满足a[i1]=b[j1], a[i2]=b[j2],….,a[in]=b[jn]
并且i1 < i2 <….< in； j1 < j2 <…< jn；
诶似乎到这里问题就变得明朗起来了，我们只需要对A序列的每个字符c，得到在B序列出现的位置，然后组成二元组用上述方法便可以解决了。
不过怎么统计在B中出现的位置呢，每个每个统计又变成n^2的复杂度了。
所以我们才说这个方法是处理一类“特殊”LCS问题嘛。
一般这类问题每个字符出现的范围很少（比如只有小写字母）,或者每个字符出现次数有限（比如A,B序列都是一个N的全排列的一种），于是我们就可以开一个数组映射就好了。
还有一个问题，如果A序列的一个字符在B中出现多次怎么办，比如 A：abbbccc B: bbccaaa
这里a在B中5 6 7位置均出现过。即（1,5）,（1,6）,（1,7）
但这三个只能选一个咋整
全选肯定是不行的，所以排序的时候若x相同则要按照y从大到小排序，那么这样就保证只会选到一个了
4.相关题目
5.最后的话
get到一个新技巧辣~~~以后有新题目或者思想也会及时更新的。
