首页 > 代码库 > BZOJ1264: [AHOI2006]基因匹配Match
BZOJ1264: [AHOI2006]基因匹配Match
1264: [AHOI2006]基因匹配Match
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 541 Solved: 347
[Submit][Status]
Description
基因匹配（match）卡卡昨天晚上做梦梦见他和可可来到了另外一个星球，这个星球上生物的DNA序列由无数种碱基排列而成（地球上只有4种），而更奇怪的是，组成DNA序列的每一种碱基在该序列中正好出现5次！这样如果一个DNA序列有N种不同的碱基构成，那么它的长度一定是5N。卡卡醒来后向可可叙述了这个奇怪的梦，而可可这些日子正在研究生物信息学中的基因匹配问题，于是他决定为这个奇怪星球上的生物写一个简单的DNA匹配程序。为了描述基因匹配的原理，我们需要先定义子序列的概念：若从一个DNA序列（字符串）s中任意抽取一些碱基（字符），将它们仍按在s中的顺序排列成一个新串u，则称u是s的一个子序列。对于两个DNA序列s1和s2，如果存在一个序列u同时成为s1和s2的子序列，则称u是s1和s2的公共子序列。卡卡已知两个DNA序列s1和s2，求s1和s2的最大匹配就是指s1和s2最长公共子序列的长度。[任务]编写一个程序：? 从输入文件中读入两个等长的DNA序列；? 计算它们的最大匹配；? 向输出文件打印你得到的结果。
Input
输入文件中第一行有一个整数N，表示这个星球上某种生物使用了N种不同的碱基，以后将它们编号为1…N的整数。以下还有两行，每行描述一个DNA序列：包含5N个1…N的整数，且每一个整数在对应的序列中正好出现5次。
Output
输出文件中只有一个整数，即两个DNA序列的最大匹配数目。
Sample Input
2
1 1 2 2 1 1 2 1 2 2
1 2 2 2 1 1 2 2 1 1
1 1 2 2 1 1 2 1 2 2
1 2 2 2 1 1 2 2 1 1
Sample Output
7
HINT
[数据约束和评分方法]
60%的测试数据中：1<=N <= 1 000
100%的测试数据中：1<=N <= 20 000
Source
题解：
这真是一道好题！
因为最传统的LCS的做法中，最大值更新的条件是 s[1][i]==s[2][j]，
而现在对于每一个 s[1][i]，我们已经知道s[2]中哪些元素与它相同，显然可以用这些元素的前缀最大值+1来更新这个点的最优值。
因为前面已经匹配过的一定是合法的，所以我们将i与该元素匹配得到一个更大的答案。
树状数组再次发挥了前缀最大值的快速查询的作用。
真是一道巧妙的题！
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm>10 11 #include<iostream>12 13 #include<vector>14 15 #include<map>16 17 #include<set>18 19 #include<queue>20 21 #include<string>22 23 #define inf 100000000024 25 #define maxn 20000+10026 27 #define maxm 500+10028 29 #define eps 1e-1030 31 #define ll long long32 33 #define pa pair<int,int>34 35 #define for0(i,n) for(int i=0;i<=(n);i++)36 37 #define for1(i,n) for(int i=1;i<=(n);i++)38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)42 43 #define mod 100000000744 45 using namespace std;46 47 inline int read()48 49 {50 51 int x=0,f=1;char ch=getchar();52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}56 57 return x*f;58 59 }60 int n,ans,p[maxn][6],s[5*maxn],f[5*maxn];61 void change(int x,int y)62 {63 for(;x<=5*n;x+=x&(-x))s[x]=max(s[x],y);64 }65 int ask(int x)66 {67 int t=0;68 for(;x;x-=x&(-x))t=max(t,s[x]);69 return t;70 }71 72 int main()73 74 {75 76 freopen("input.txt","r",stdin);77 78 freopen("output.txt","w",stdout);79 80 n=read();81 for1(i,5*n){int x=read();p[x][++p[x][0]]=i;}82 for1(i,5*n)83 {84 int x=read();85 for3(j,5,1)86 {87 int y=p[x][j],t=ask(y-1)+1;88 if(t>f[y])f[y]=t,change(y,t);89 }90 }91 for1(i,5*n)ans=max(ans,f[i]);92 printf("%d\n",ans);93 94 return 0;95 96 }
BZOJ1264: [AHOI2006]基因匹配Match
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。