bzoj2764 基因补全

时间:2022-11-03 12:09:09

Description

在生物课中我们学过,碱基组成了DNA(脱氧核糖核酸),他们分别可以用大写字母A,C,T,G表示,其中A总与T配对,C总与G配对。两个碱基序列能相互匹配,当且仅当它们等长,并且任意相同位置的碱基都是能相互配对的。例如ACGTC能且仅能与TGCAG配对。一个相对短的碱基序列能通过往该序列中任意位置补足碱基来与一个相对长的碱基序列配对。补全碱基的位置、数量不同,都将视为不同的补全方案。现在有两串碱基序列S和T,分别有n和m个碱基(n>=m),问一共有多少种补全方案。

Input

数据包括三行。
第一行有两个整数n,m,表示碱基序列的长度。
第二行包含n个字符,表示碱基序列S。
第三行包含m个字符,表示碱基序列T。
两个碱基序列的字符种类只有A,C,G,T这4个大写字母。

Output

答案只包含一行,表示补全方案的个数。
dp+高精度
把第二个串换为与其配对的串
若s1[i]==s2[j]则 f[i][j]=f[i-1][j]+f[i-1][j-1]
否则 f[i][j]=f[i-1][j]
使用滚动数组以节约空间
#include<cstdio>
#include<cstring>
int n,m;
char s1[],s2[];
char ch[];
int f[][];
int main(){
scanf("%d%d",&n,&m);
scanf("%s%s",s1+,s2+);
ch['A']='T';ch['T']='A';ch['G']='C';ch['C']='G';
for(int i=;i<=m;i++)s2[i]=ch[s2[i]];
f[][]=;
for(int i=;i<=n;i++){
for(int j=m;j;j--){
if(s1[i]==s2[j]){
int*w=f[j];
for(int x=;x<;x++)w[x]+=f[j-][x];
for(int x=;x<;x++){
if(w[x-]>=)
++w[x],w[x-]-=;
}
}
}
}
bool d=;
for(int i=;i>=;i--){
if(d)printf("%09d",f[m][i]);
if(f[m][i]&&!d)printf("%d",f[m][i]),d=;
}
if(!d)puts("");
return ;
}

bzoj2764 基因补全的更多相关文章

  1. 2764&colon; &lbrack;JLOI2011&rsqb;基因补全

    2764: [JLOI2011]基因补全 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 570  Solved: 187[Submit][Status ...

  2. &lbrack;JLOI2011&rsqb;基因补全

    1973: [JLOI2011]基因补全 Time Limit: 1 Sec  Memory Limit: 256 MB Description 在生物课中我们学过,碱基组成了DNA(脱氧核糖核酸), ...

  3. BZOJ&lowbar;2764&lowbar;&lbrack;JLOI2011&rsqb;基因补全&lowbar;DP&lowbar;高精度

    BZOJ_2764_[JLOI2011]基因补全_DP_高精度 Description 在生物课中我们学过,碱基组成了DNA(脱氧核糖核酸),他们分别可以用大写字母A,C,T,G表示,其中A总与T配对 ...

  4. 【bzoj2764】&lbrack;JLOI2011&rsqb;基因补全 dp&plus;高精度

    题目描述 在生物课中我们学过,碱基组成了DNA(脱氧核糖核酸),他们分别可以用大写字母A,C,T,G表示,其中A总与T配对,C总与G配对.两个碱基序列能相互匹配,当且仅当它们等长,并且任意相同位置的碱 ...

  5. BZOJ2764 &lbrack;JLOI2011&rsqb;基因补全

    Description 在 生物课中我们学过,碱基组成了DNA(脱氧核糖核酸),他们分别可以用大写字母A,C,T,G表示,其中A总与T配对,C总与G配对.两个碱基序列能相互 匹配,当且仅当它们等长,并 ...

  6. Oracle补全日志&lpar;Supplemental logging&rpar;

    Oracle补全日志(Supplemental logging)特性因其作用的不同可分为以下几种:最小(Minimal),支持所有字段(all),支持主键(primary key),支持唯一键(uni ...

  7. python 添加tab补全

    在平时查看Python方法用到tab补全还是很方便的. 1. mac 平台 配置如下: mac是类Unix平台,需要在添加一条配置内容到bash_profile 中(默认是没有这个文件,可以新建一个放 ...

  8. 记录一次bug解决过程:else未补全导致数据泄露和代码优化

    一.总结 快捷键ctrl + alt + 四个方向键 --> 倒置屏幕 未补全else逻辑,倒置查询数据泄露 空指针是最容易犯的错误,数据的空指针,可以普遍采用三目运算符来解决 SVN冲突解决关 ...

  9. jQuery 邮箱下拉列表自动补全

    综述 我想大家一定见到过,在某个网站填写邮箱的时候,还没有填写完,就会出现一系列下拉列表,帮你自动补全邮箱的功能.现在我们就用jQuery来实现一下. 博主原创代码,如有代码写的不完善的地方还望大家多 ...

随机推荐

  1. JavaScript第一天

    1.静态的网页技术和动态的网页技术 静态网页是相对于动态网页而言,是指没有后台数据库.不含程序和不可交互的网页.你编的是什么它显示的就是什么.不会有任何改变.静态网页相对更新起来比较麻烦,适用于一般更 ...

  2. &lbrack;ZZ&rsqb; RGBM and RGBE encoding for HDR

    Deferred lighting separate lighting rendering and make lighting a completely image-space technique. ...

  3. 刀哥多线程串行队列gcd-04-dispatch&lowbar;queue&lowbar;serial

    串行队列 特点 以先进先出的方式,顺序调度队列中的任务执行 无论队列中所指定的执行任务函数是同步还是异步,都会等待前一个任务执行完成后,再调度后面的任务 队列创建 dispatch_queue_t q ...

  4. 从零开始写一个Tomcat&lpar;贰&rpar;--建立动态服务器

    上文书说道如何通过http协议建立一个静态的服务器来访问静态网页,但我们选择tomcat最主要的原因还是因为它能动态的执行servlet,这边文章将引导你实现一个能够运行servlet的服务器,这个简 ...

  5. 【转】如何使用Git上传本地项目到github&quest;&lpar;mac版&rpar;

    原文链接:http://www.cnblogs.com/lijiayi/p/pushtogithub.html 在此假设你已经在 github 上创建好了一个项目,像这样: 并且你已经完成了自己的项目 ...

  6. backgroud背景色样式兼容ie8 rgba&lpar;&rpar;用法

    今天遇到了一个问题,要在一个页面中设置一个半透明的白色div.这个貌似不是难题,只需要给这个div设置如下的属性即可: background: rgba(255,255,255,.1);但是要兼容到i ...

  7. 解决JSON&period;stringify&lpar;&rpar;自动将中文转译成unicode的方法

    最近在工作中,发现在IE8下JSON.stringify()自动将中文转译为unicode编码,原本选择的中文字符,传到后台变为了unicode编码,即\u****的形式.查找资料后发现,与标准的JS ...

  8. Hadoop HDFS 用java API 进行读写

    public class HdfsApp { public static FileSystem getFileSystem() throws Exception { Configuration con ...

  9. Django--Session 操作

    Session Session的由来 Cookie虽然在一定程度上解决了“保持状态”的需求,但是由于Cookie本身最大支持4096字节,以及Cookie本身保存在客户端,可能被拦截或窃取,因此就需要 ...

  10. 一、JDBC

    一.CRUD(增删改查) C:增加Create R查询(Retrieve) U更新(Update) D删除(Delete) 在JDBC中,增加,删除,修改,操作都基本一样,只是传递不同SQL语句,最后 ...