2764: [JLOI2011]基因补全

2764: [JLOI2011]基因补全

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 570  Solved: 187

[Submit][Status][Discuss]

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

答案只包含一行,表示补全方案的个数。

Sample Input

10 3 CTAGTAGAAG TCC

Sample Output

4

HINT

样例解释:

TCC的4种补全方案(括号中字符为补全的碱基)

(GA)TC(AT)C(TTC)

(GA)TC(ATCTT)C

(GA)T(CAT)C(TT)C

(GATCA)TC(TT)C

数据范围:

30%数据n<=1000,m<=2

50%数据n<=1000,m<=4

100%数据n<=2000,m<=n

Source

题解:一道萌萌哒DP问题,引用某神犇的题解

题解:  可以考虑算出序列T在序列S里匹配的本质不同方案数,利用dp可以很容易解决这个问题。  令f[i][j]表示序列S前i位匹配序列T至第j位的方案数,则对于f[i][j],若不用S[i]匹配T[j],则为f[i−1][j],若能匹配,则可由f[i−1][j−1]转化至该状态,最终的答案为f[n][m],dp可滚动。 

然后关键来了——数量是完全可能超过\( {2}^{64} \)的,所以可以,或者说必须进行高精度运算,害得我狂WA不止

然后我写了个萌萌哒高精度,于是还是狂WA不止(下面那个数组开炸了请无视TT)

然后最后发现是高精度加法里面没清零= =,然后

没有然后了

 1 /**************************************************************
 2     Problem: 2764
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:4380 ms
 7     Memory:4168 kb
 8 ****************************************************************/
 9  
10 type
11     arr=array[0..500] of longint;
12 var
13    i,j,k,l,m,n:longint;ch:char;
14    c:array[0..2005] of arr;
15    a,b:array[0..2005] of longint;
16 function max(x,y:longint):longint;
17          begin
18               if x>y then max:=x else max:=y;
19          end;
20 function add(a,b:arr):arr;
21          var c:arr;i,j,k:longint;
22          begin
23               fillchar(c,sizeof(c),0);
24               c[0]:=max(a[0],b[0])+1;k:=0;
25               for i:=1 to c[0] do
26                   begin
27                        k:=k+a[i]+b[i];
28                        c[i]:=k mod 10;
29                        k:=k div 10;
30                   end;
31               while k>0 do
32                     begin
33                          inc(c[0]);
34                          c[c[0]]:=k mod 10;
35                          k:=k div 10;
36                     end;
37               while (c[0]>1) and (c[c[0]]=0) do dec(c[0]);
38               exit(c);
39          end;
40 procedure outp(a:arr);
41           var i:longint;
42           begin
43                for i:=a[0] downto 1 do write(a[i]);
44                writeln;
45           end;
46 function trans(ch:char):longint;
47          begin
48               case upcase(ch) of
49                    'A':exit(1);
50                    'C':exit(2);
51                    'T':exit(4);
52                    'G':exit(3);
53               end;
54          end;
55 begin
56      readln(n,m);
57      for i:=1 to n do
58          begin
59               read(ch);
60               a[i]:=5-trans(ch);
61          end;
62      readln;
63      for i:=1 to m do
64          begin
65               read(ch);
66               b[i]:=trans(ch);
67          end;
68      readln;fillchar(c[0],sizeof(c[0]),0);c[0][0]:=1;c[0][1]:=1;
69      for i:=1 to n do
70          for j:=m downto 1 do
71              if a[i]=b[j] then c[j]:=add(c[j],c[j-1]);
72      outp(c[m]);
73      readln;
74 end.    

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏高爽的专栏

POI读取Excel常见问题

       最近在做一个将excel导入到报表中的功能,使用了POI来实现,发现POI使用有诸多不便之处,先记录下来,以后可能考虑使用Openxml。    ...

2700
来自专栏java系列博客

HibernateCallback 的用法

1162
来自专栏懒人记的专栏

如何用 Go 实现单链表

每节运煤车就是单链表里的元素,每节车厢里的煤炭就是元素中保存的数据。前后车通过锁链相连,作为单链表运煤车,从1号车厢开始,每节车厢都知道后面拉着哪一节车厢,却不...

4910
来自专栏算法修养

CodeForces 651 C Watchmen

C. Watchmen time limit per test 3 seconds memory limit per test 256 megaby...

2743
来自专栏Android知识点总结

Java总结IO之总集篇

字符流和字节流向来各行其事,很少有交集。 但Reader和Writer有两个奇子,名叫InputStreamReader(男)和OutputStreamWri...

1415
来自专栏数据结构与算法

P2580 于是他错误的点名开始了

题目背景 XS中学化学竞赛组教练是一个酷爱炉石的人。 他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次,然后正好被路过的校长发现了然后就是一顿欧拉欧拉...

3087
来自专栏Jerry的SAP技术分享

使用com.sun.imageio.plugins.png.PNGMetadata读取图片的元数据

所谓图片元数据,就是除了我们肉眼看到的图片内容外,隐藏在这些内容背后的一些技术数据。

1594
来自专栏码匠的流水账

聊聊eureka client的fetch-remote-regions-registry属性

本文主要研究一下eureka client的fetch-remote-regions-registry属性

1551
来自专栏闵开慧

javascript入门操作

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.or...

38413
来自专栏LhWorld哥陪你聊算法

Hadoop源码篇--Reduce篇

Reduce文件会从Mapper任务中拉取很多小文件,小文件内部有序,但是整体是没序的,Reduce会合并小文件,然后套个归并算法,变成一个整体有序的文件。

2621

扫码关注云+社区

领取腾讯云代金券