# 2764: [JLOI2011]基因补全

## 2764: [JLOI2011]基因补全

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 570  Solved: 187

[Submit][Status][Discuss]

## Sample Input

10 3 CTAGTAGAAG TCC

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

``` 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.    ```

251 篇文章37 人订阅

0 条评论

## 相关文章

### POI读取Excel常见问题

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

2700

1162

4910

### CodeForces 651 C Watchmen

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

2743

1415

3087

1594

1551

### javascript入门操作

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

38413

### Hadoop源码篇--Reduce篇

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

2621