[JLOI2011]基因补全

1973: [JLOI2011]基因补全

Time Limit: 1 Sec Memory Limit: 256 MB

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

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

这道题需要用到高精度，在高精度的同时做LCS，记得要用滚动数组，否则有可能MLE

  1 #include<stdio.h>
  2 char a[2001],b[2001];
  3 int n_a[2001],n_b[2001];
  4 int f[2001][2001];
  5 int how_many[2][2001][100];
  6 int n,m;
  7 int max(int a,int b)
  8 {
  9     if(a>b)
 10         return a;
 11     return b;
 12 }
 13 int min(int a,int b)
 14 {
 15     if(a<b)
 16         return a;
 17     return b;
 18 }
 19 void add(int a,int b,int c,int d)
 20 {
 21     int tmp=max(how_many[c][d][0],how_many[a][b][0]);
 22     int middle=0;
 23     int middle2;
 24     for(int i=1;i<=tmp;i++)
 25     {
 26         middle2=(how_many[c][d][i]+how_many[a][b][i]+middle)/1000000000;
 27         how_many[a][b][i]=(how_many[c][d][i]+how_many[a][b][i]+middle)%1000000000;
 28         middle=middle2;
 29     }
 30     how_many[a][b][0]=tmp;
 31     while(middle)
 32     {
 33         how_many[a][b][++how_many[a][b][0]]=middle%1000000000;
 34         middle/=1000000000;
 35     }
 36 }/*高精度求和*/
 37 int main()
 38 {
 39     scanf("%d%d",&n,&m);
 40     scanf("%s",a);
 41     scanf("%s",b);
 42     for(int i=0;i<n;i++)
 43     {
 44         if(a[i]=='A')
 45         {
 46             n_a[i+1]=2;
 47         }
 48         else if(a[i]=='T')
 49         {
 50             n_a[i+1]=1;
 51         }
 52         else if(a[i]=='G')
 53         {
 54             n_a[i+1]=4;
 55         }
 56         else if(a[i]=='C')
 57         {
 58             n_a[i+1]=3;
 59         }
 60         how_many[i%2][0][0]=1;
 61         how_many[i%2][0][1]=1;
 62     }/*将a字符的字母转换成可以匹配的形式，方便进行LCS*/
 63     for(int i=0;i<m;i++)
 64     {
 65         if(b[i]=='A')
 66         {
 67             n_b[i+1]=1;
 68         }
 69         else if(b[i]=='T')
 70         {
 71             n_b[i+1]=2;
 72         }
 73         else if(b[i]=='G')
 74         {
 75             n_b[i+1]=3;
 76         }
 77         else if(b[i]=='C')
 78         {
 79             n_b[i+1]=4;
 80         }
 81         how_many[0][i][0]=1;
 82         how_many[0][i][1]=1;
 83     }
 84     how_many[0][0][1]=1;
 85     for(int i=1;i<=n;i++)
 86     {
 87         for(int j=1;j<=m;j++)
 88         {
 89             for(int k=how_many[i%2][j][0];k>=0;k--)
 90                 how_many[i%2][j][k]=0;
 91             if(n_a[i]==n_b[j])
 92             {
 93                 if(f[i-1][j-1]+1>=f[i-1][j]&&f[i-1][j-1]+1>=f[i][j-1])
 94                 {
 95                     f[i][j]=f[i-1][j-1]+1;
 96                 }
 97                 else if(f[i-1][j-1]+1<=f[i-1][j]&&f[i-1][j]>=f[i][j-1])
 98                 {
 99                     f[i][j]=f[i-1][j];
100                 }
101                 else if(f[i][j-1]>=f[i-1][j]&&f[i-1][j-1]+1<=f[i][j-1])
102                 {
103                     f[i][j]=f[i][j-1];
104                 }
105                 if(f[i][j]==f[i-1][j-1]+1)
106                 {
107                     add(i%2,j,(i-1)%2,j-1);
108                 }
109                 if(f[i][j]==f[i-1][j])
110                 {
111                     add(i%2,j,(i-1)%2,j);
112                 }
113                 if(f[i][j]==f[i][j-1])
114                 {
115                     add(i%2,j,i%2,j-1);
116                 }
117             }
118             else
119             {
120                 if(f[i-1][j]>=f[i][j-1])
121                 {
122                     f[i][j]=f[i-1][j];
123                 }
124                 else if(f[i][j-1]>=f[i-1][j])
125                 {
126                     f[i][j]=f[i][j-1];
127                 }
128                 if(f[i][j]==f[i-1][j])
129                 {
130                     add(i%2,j,(i-1)%2,j);
131                 }
132                 if(f[i][j]==f[i][j-1])
133                 {
134                     add(i%2,j,i%2,j-1);
135                 }
136             }
137         }
138     }/*LCS加上求方案数*/
139     for(int i=how_many[n%2][m][0];i;i--)
140     {
141         if(i!=how_many[n%2][m][0])
142             printf("%09d",how_many[n%2][m][i]);
143         else
144             printf("%d",how_many[n%2][m][i]);
145     }/*高精度输出*/
146 }