[模板]LCS最长公共子序列
luoguP1439,本身不算难,记一下防止自己下次看到不会做 qwq # 题意 给出 1 到 n 的两组全排列,求它们的最长公共子序列。 # 最长上升子序列 LIS 朴素做法:f [i] 到第 i 个元素的 LIS 长度,n 方做即可。 二分做法:f [i] 表示长度为 i 的上升子序列,每次对于一个新的元素,二分查出比这个值大的第一个值,去更新 f 数组。 rep (i, 1, n){ int l = 0, r = mx, mid; // 可以扩展最大长度 if (a[i] > f[mx]) f[++mx] =...
more...