简单子序列相关问题
1.求最长公共子序列：
\[
f_i= \max_{1≤j<i∧a_j<a_i} f_j+1
\]
朴素做法：\(O(n^2)\)
数据结构优化或二分优化：\(O(n\log n)\)
相关变形例题：
3.友好城市
2.子序列计数：
求长度为K的上升子序列个数
\(f_{i,j}\)以\(a_i\)为上升子序列末项，长度为\(j\)的上升子序列个数 $$ f_{i,j}=\sum_{k=1}^{i-1}f_{k,j-1}[a_k<a_i] $$ 朴素做法：\(O(n^2k)\)
数据结构(树状数组)优化：\(O(nk\log n)\)
（一个上升子序列的所有数的集合可以与另一个上升子序列的所有数的集合相同，如果同时存在于一个序列，都为合法上升子序列，都算入贡献）（可重复）
相关变形例题：
2.低价购买（LIS的计数）（不重复）
3.[TJOI2014] 上升子序列（不重复）
3.拆序列问题：
将一个序列拆成两个具有单调性的子序列
相关变形例题：
1.子序列
4.LCS：
相关变形例题：
1.LCS
\(by\) \(Rubbish\_Du\)