[关闭]
@ysner 2018-11-04T22:26:20.000000Z 字数 1408 阅读 1949

[AHOI2006]基因匹配

DP LCS 树状数组


题面

给出两个数列,它们都包含种元素,并且每种元素都恰有个,求它们的最长公共子序列。

解析

一般的求法是的。
表示在中匹配到第个,中匹配到第个。

  1. fp(i,1,n)
  2. fp(j,1,n)
  3. {
  4. f[i][j]=max(f[i][j-1],f[i-1][j]);
  5. if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
  6. }

但是有时可以转化为来做。
假设有两个序列

记录中每个元素在中出现的位置, 再将位置按降序排列, 则上面的例子可表示为:

中每个元素的位置按中元素的顺序排列成一个序列

再对得到的值即为求的答案。

感觉这有点像一种等效替代,倒序实际上保证了不能自己向自己转移。

这题转化为问题后序列长度为,用算法可以解决。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;++i)
  11. #define fq(i,a,b) for(re int i=a;i>=b;--i)
  12. using namespace std;
  13. const int N=5e5+100;
  14. int n,m,pre[N][6],f[N],sta[N],t[N],top,ans;
  15. il ll gi()
  16. {
  17. re ll x=0,t=1;
  18. re char ch=getchar();
  19. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  20. if(ch=='-') t=-1,ch=getchar();
  21. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  22. return x*t;
  23. }
  24. il int max(re int x,re int y){return x>y?x:y;}
  25. il void upd(re int x,re int w){for(;x<=n;x+=x&-x) t[x]=max(t[x],w);}
  26. il int que(re int x){re int res=0;for(;x;x-=x&-x) res=max(res,t[x]);return res;}
  27. int main()
  28. {
  29. m=gi();n=m*5;
  30. fp(i,1,n)
  31. {
  32. re int x=gi();
  33. pre[x][++pre[x][0]]=i;
  34. }
  35. fp(i,1,n)
  36. {
  37. re int x=gi();
  38. fq(j,5,1) sta[++top]=pre[x][j];
  39. }
  40. fp(i,1,top)
  41. f[i]=que(sta[i]-1)+1,upd(sta[i],f[i]),ans=max(ans,f[i]);
  42. printf("%d\n",ans);
  43. return 0;
  44. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注