题解 P1439 【【模板】最长公共子序列】

提供一种很简单的做法，代码也很简单。 前置要求：树状数组 由于两个序列 $P_1$ ， $P_2$ 都是 $1$ ~ $n$ 的排列，我们可以很简单地处理出序列 $P_1$ 中第 $i$ 个数在 $P_2$ 中出现时所处位置的下标 $place[i]$，即 $P_1[i]=P_2[place[i]]$ 。 使 $f[i]$表示以 $P_2$ 中第 $i$ 个数结尾的最长公共子序列长度。正序扫描 $P_1$ ，那么处理到 $P_1$的第 $i$ 个数时就有: >$f[place[i]]=max(f[k])+1$ , $k∈[1,place[i])$ 稍微解释一下上面的式子(如果你可以理解请跳过本段): 在处理 $P_1$ 的第 $i$ 个数 $P_1[i]$ 时，以$P_1[j]$ **(** $j∈[1,i)$ **)** 结尾的最长公共子序列均在f[place[j]]中储存着 。此时 $i>j$ ，如果同时有 $place[i]>place[j]$ ，那么 $P_1[i]$ 就可以接在 $P_1[j]$ 后面，公共子序列长度加一，因此以 $P_1[i]$ 结尾的最长公共子序列长度就是$max(f[k])+1$ **(** $k∈[1,place[i])$ **)** 了。 用树状数组处理$f$数组的前缀最大值即可在$O(nlog_2n)$的时间复杂度内完成本题，最后的答案就是$max(f[i])$。$(i∈[1,n])$ $Code:$ ```cpp #include<iostream> #include<cstdio> #include<cmath> using namespace std; int n,ans,a[100010],b[100010],place[100010],tree[100010]; //树状数组基本操作 query和add inline int query(int x)//询问前缀max { for(ans=0;x;x-=(x&-x)) ans=max(ans,tree[x]); return ans; } inline void add(int v,int pos)//在pos位置更新最大值 v { for(;pos<=n;pos+=(pos&-pos)) tree[pos]=max(tree[pos],v); } int main() { scanf("%d",&n); for(register int i=1;i<=n;i++) scanf("%d",&a[i]); for(register int i=1;i<=n;i++) scanf("%d",&b[i]),place[b[i]]=i; for(register int i=1;i<=n;i++) add(query(place[a[i]]-1)+1,place[a[i]]); printf("%d",query(n)); return 0; } ``` 个人感觉代码的结构很清晰，不是很明白的话可以私我QwQ。