[数据约束和评分方法]
60%的测试数据中：1<=N <= 1 000
100%的测试数据中：1<=N <= 20 000
【思路】
DP+树状数组。
计算最长公共子序列的朴素算法时间为O(n^2)。
注意到题目中每个数字都会出现5次的特点：记录5个数字分别出现的位置pos[][5]，扫描b序列，对于b[i]找到在a中与其对应数字的5个位置，该5个位置都可以被b[i]更新，转移式为：
f[k]=max{f[j]},1<=j<=k-1
计算区间最大值可以用Fenwick tree简单实现。
注意到j的枚举必须是倒序的，防止覆盖。
【代码】
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 5 const int maxn = 100000+10; 6 7 int f[maxn],pos[maxn][6],a[maxn],b[maxn]; 8 int n; 9 10 int c[maxn]; 11 int lowbit(int x) { return x&(-x); } 12 void update(int x,int v) { 13 while(x<=n) 14 c[x]=max(c[x],v) , x+=lowbit(x); 15 } 16 int query(int x) { 17 int ans=0; 18 while(x) ans=max(ans,c[x]) , x-=lowbit(x); 19 return ans; 20 } 21 22 int main() { 23 scanf("%d",&n); 24 n*=5; 25 for(int i=1;i<=n;i++) { 26 scanf("%d",&a[i]); 27 pos[a[i]][++pos[a[i]][0]]=i; 28 } 29 for(int i=1;i<=n;i++) scanf("%d",&b[i]); 30 int ans=0; 31 for(int i=1;i<=n;i++) 32 for(int j=5;j;j--) { 33 int k=pos[b[i]][j]; 34 f[k]=max(f[k],query(k-1)+1); 35 update(k,f[k]); 36 ans=max(ans,f[k]); 37 } 38 printf("%d\n",ans); 39 return 0; 40 }
bzoj 1264 [AHOI2006]基因匹配Match（DP+树状数组）
原文：http://www.cnblogs.com/lidaxin/p/5099899.html