[luoguP3402] 最长公共子序列（DP + 离散化 + 树状数组）

传送门

比P1439排列LCS问题，难那么一点点，只不过有的元素不是两个串都有，还有数据范围变大，树状数组得打离散化。

不过如果用栈+二分的话还是一样的。

——代码

1 #include <cstdio> 2 #include <algorithm> 3 4 const int MAXN = 300001; 5 int n, m, size, ans; 6 int a[MAXN], b[MAXN], c[MAXN << 1], q[MAXN << 1], p[MAXN << 1]; 7 8 inline int max(int x, int y) 9 12 13 inline int query(int x) 14 19 20 inline void update(int x, int d) 21 24 25 int main() 26 39 for(i = 1; i <= n; i++) 40 if(p[a[i]]) 41 46 printf("%d", ans); 47 return 0; 48 }
View Code

上一篇：[luoguP2885] [USACO07NOV]电话线Telephone Wire（DP + 贪心）

下一篇：矩阵运算所满足的定律

---

DP 树状数组 离散化