传送门
无重复元素的LCS问题
n2 做法不说了。
nlogn 做法 ——
因为LCS问题求的是公共子序列，顺序不影响答案，影响答案的只是两个串的元素是否相同，所以可以交换元素位置。
首先简化一下问题，假设P1恰好为单调递增的1,2,3,...n，那么很显然答案就是P2的最长上升子序列的长度
问题是P1并非单调递增的，但我们可以假定它就是1,2,3,...,n。
也就是重新定义一下第一个串中 所有数 的顺序，定义a[x] = i，也就是 数x 是第 i 个，然后再重新弄一下第二串的顺序，最后求一遍lis。
——代码
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 5 using namespace std; 6 7 const int MAXN = 100001; 8 int n, ans; 9 int a[MAXN], b[MAXN], c[MAXN]; 10 11 inline int query(int x) 12 17 18 inline void update(int x, int d) 19 22 23 int main() 24 35 printf("%d", ans); 36 return 0; 37 }View Code
还有另一种思路。也是 nlogn，而且比较好理解。（说实话，我真不理解上面的映射是怎么弄的）
原本 n2做法是设 f[i][j] 表示 第一串的前 i 个数 和 第二串的前 j 个数 的最优答案（i 和 j 都不必须选），然后一阵乱搞。
nlogn——
可以改变状态的定义，f[i][j] 表示第一串的前 i 个数 和 第二串的前 j 个数 的最有答案（i 不必须选，j 必须选）
这样 f[i][] 只能由 f[i 1][] 转移过来，这样就变成了分层的DP，并且只转移到 f[i][k] （其中 b[k] == a[i]），也就是只影响一个答案。
所以先记录和 a[i] 相同的 b[j] 的位置，然后 f 数组可以变成一维，动态维护 f 数组即可。
f[i] = max(f[j]) + 1 ( 1 <= j < i && a[i] == b[j])
——代码
1 #include <cstdio> 2 #include <iostream> 3 4 using namespace std; 5 6 const int MAXN = 100001; 7 int n, ans; 8 int a[MAXN], b[MAXN], c[MAXN], p[MAXN], f[MAXN]; 9 10 inline int query(int x) 11 16 17 inline void update(int x, int d) 18 21 22 int main() 23 34 printf("%d", ans); 35 return 0; 36 }View Code
上一篇：[luoguP2216] [HAOI2007]理想的正方形（二维单调队列）
下一篇：[luoguP1082] 同余方程（扩展欧几里得）
DP 树状数组
