基础
最长上升子序列 DP有O(n^2)
最长公共子序列 DP有O(n^2)
进阶
最长上升子序列 O(nlogn) 二分
上升本身是一个很强的性质,
对于一个不同的答案数列1~n,其中任何一个长度为i的序列维护末尾最小的数会比其它数更优,
所以有了O(n^2)的算法
最长公共子序列 O(n^2/w) bitset 做法
(还有一个 O(nlogn)的算法,但只是针对排列的情况,就是转换成最长上升子序列。
回归正题,
答案f数组性质是同一行同一列单调不减,并且相邻两个不超过一。
如果对f每行分别进行差分,就可以得到一个01数组g。
用bitset维护g,但这样还是无法转移。
所以我们又定义了bitset数组p维护在字符串A中各字符出现的所有位置的集合。
最大匹配也是一个类似贪心的问题,转移过程手画一下就清晰了。