题意

给出两个长度为5*n的序列，每个序列中[1,n]每个元素恰好出现5次。问其最长公共子序列。 n<=20000

分析

枚举第一个序列，设f[i]表示到当前时刻，第二个序列中最后一位为第i位的最长公共子序列的长度是多少。然后用树状数组来加速转移即可。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int N=100005; int n,pos[N/5][6],c[N],tot[N/5]; void ins(int x,int y) { while (x<=n) c[x]=max(c[x],y),x+=x&(-x); } int query(int x) { int ans=0; while (x) ans=max(ans,c[x]),x-=x&(-x); return ans; } int main() { scanf("%d",&n);n*=5; for (int i=1;i<=n;i++) { int x; scanf("%d",&x); tot[x]++;pos[x][tot[x]]=i; } for (int i=1;i<=n;i++) { int x; scanf("%d",&x); for (int j=5;j>=1;j--) ins(pos[x][j],query(pos[x][j]-1)+1); } printf("%d",query(n)); return 0; }