BZOJ 1264 [AHOI2006]基因匹配Match DP+BIT

2024-03-30 17:08

本文主要是介绍BZOJ 1264 [AHOI2006]基因匹配Match DP+BIT,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

Sample Output

7

HINT

[数据约束和评分方法]
60%的测试数据中:1<=N <= 1 000
100%的测试数据中:1<=N <= 20 000

Source



原题链接
恭喜啊!bzoj终于50题了……(蒟蒻)


题意是很清晰的,1~n每个数字出现5次,给出两个不同的数组,求它们的LCS。
最大的数据中,数组长度有10^5,求LCS的O(N^2)算法肯定是不行的了。

考虑一下题目的特性:每个数字恰好出现5次。
我们在dp的时候,当a[u]=b[v],可以dp[u][v]转移。
只有相等的时候才可以!
而这题里每个数字出现5次,
所以事实上,对于每一个b[i],我们能够在a[]里面找出5个位置。
而这5个位置是可以提前记录下来的。
这样子,我们的dp转移也可以压缩到一维,然后对于每一个b[i],直接在dp[]里转移。

太含糊了,比如说:
1 2 1 2 1 1 1 2 2 2
1 1 1 1 1 2 2 2 2 2
答案是8.
我们dp[u]表示a[]里面,第u个位置前面能够匹配最长长度dp[u].
然后b[1]=1,我们就更新a[]每个1位置u的dp[u]
dp[u]=Max(dp[v])+1,1<=v<u
注意要倒着来,想法比较简单,具体不赘述了。
1 0 1 0 1 1 1 0 0 0
然后第2个1,同样找这些位置,dp更新为
1 0 2 0 2 2 2 0 0 0
……

差不多酱紫吧……

然后可以看到有一个找最大值的过程。
维护一个数据结构就好了……树状数组就够了,反正1~k的max。

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0,f=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
const int N=20005;
int n;
int cnt[N][10];
int tree[N*5],f[N*5];
int lowbit(int x){return x&(-x);
}
void upd(int x,int y){for (int i=x;i<=5*n;i+=lowbit(i))tree[i]=max(tree[i],y);
}
int Max(int x){int t=0;for (int i=x;i;i-=lowbit(i))t=max(t,tree[i]);return t;
}
void update(int x){f[x]=Max(x-1)+1;upd(x,f[x]);
}
int main(){n=read();int tmp;for (int i=1;i<=5*n;i++){tmp=read();cnt[tmp][++cnt[tmp][0]]=i;}for (int i=1;i<=5*n;i++){tmp=read();for (int j=5;j;j--)update(cnt[tmp][j]);} int ans=0;for (int i=1;i<=5*n;i++)ans=max(ans,f[i]);printf("%d\n",ans);return 0;
}


这篇关于BZOJ 1264 [AHOI2006]基因匹配Match DP+BIT的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/862073

相关文章

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

MySql match against工具详细用法

《MySqlmatchagainst工具详细用法》在MySQL中,MATCH……AGAINST是全文索引(Full-Textindex)的查询语法,它允许你对文本进行高效的全文搜素,支持自然语言搜... 目录一、全文索引的基本概念二、创建全文索引三、自然语言搜索四、布尔搜索五、相关性排序六、全文索引的限制七

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

Python中使用正则表达式精准匹配IP地址的案例

《Python中使用正则表达式精准匹配IP地址的案例》Python的正则表达式(re模块)是完成这个任务的利器,但你知道怎么写才能准确匹配各种合法的IP地址吗,今天我们就来详细探讨这个问题,感兴趣的朋... 目录为什么需要IP正则表达式?IP地址的基本结构基础正则表达式写法精确匹配0-255的数字验证IP地

浅谈配置MMCV环境,解决报错,版本不匹配问题

《浅谈配置MMCV环境,解决报错,版本不匹配问题》:本文主要介绍浅谈配置MMCV环境,解决报错,版本不匹配问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录配置MMCV环境,解决报错,版本不匹配错误示例正确示例总结配置MMCV环境,解决报错,版本不匹配在col

详解nginx 中location和 proxy_pass的匹配规则

《详解nginx中location和proxy_pass的匹配规则》location是Nginx中用来匹配客户端请求URI的指令,决定如何处理特定路径的请求,它定义了请求的路由规则,后续的配置(如... 目录location 的作用语法示例:location /www.chinasem.cntestproxy

python之流程控制语句match-case详解

《python之流程控制语句match-case详解》:本文主要介绍python之流程控制语句match-case使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录match-case 语法详解与实战一、基础值匹配(类似 switch-case)二、数据结构解构匹

Nginx中location实现多条件匹配的方法详解

《Nginx中location实现多条件匹配的方法详解》在Nginx中,location指令用于匹配请求的URI,虽然location本身是基于单一匹配规则的,但可以通过多种方式实现多个条件的匹配逻辑... 目录1. 概述2. 实现多条件匹配的方式2.1 使用多个 location 块2.2 使用正则表达式

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中,括号匹配是一个常见问题,尤其是在