首页 > 代码库 > [luoguP1439] 排列LCS问题（DP + 树状数组）
[luoguP1439] 排列LCS问题（DP + 树状数组）
传送门
无重复元素的LCS问题
n2 做法不说了。
nlogn 做法 ——
因为LCS问题求的是公共子序列，顺序不影响答案，影响答案的只是两个串的元素是否相同，所以可以交换元素位置。
首先简化一下问题，假设P1恰好为单调递增的1,2,3,...n，那么很显然答案就是P2的最长上升子序列的长度
问题是P1并非单调递增的，但我们可以假定它就是1,2,3,...,n，将P1[1]映射到1，P1[2]映射到2，……然后再将P2作相同的变换即可，这样只要求P2的最长上升子序列了。
——代码
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 {13 int ans = 0;14 for(; x; x -= x & -x) ans = max(ans, c[x]);15 return ans;16 }17 18 inline void update(int x, int d)19 {20 for(; x <= n; x += x & -x) c[x] = max(c[x], d);21 }22 23 int main()24 {25 int i, j, x, y;26 scanf("%d", &n);27 for (i = 1; i <= n; i++) scanf("%d", &x), a[x] = i;28 for (i = 1; i <= n; i++) scanf("%d", &x), b[i] = a[x];29 for(i = 1; i <= n; i++)30 {31 y = query(b[i] - 1) + 1;32 update(b[i], y);33 ans = max(ans, y);34 }35 printf("%d", ans);36 return 0;37 }
[luoguP1439] 排列LCS问题（DP + 树状数组）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。