【bzoj2764】[JLOI2011]基因补全

2015.02.02 15:25 Mon | 3次阅读 | 旧日oi | 固定链接 | 源码

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

题解

很水的dp,dp[i][j]表示前i个字符中匹配了j个的方案数,转移就是dp[i][j]=dp[i-1][j]+dp[i-1][j-1],第二项看当前字符是否和第二个串的第j个字符相等,相等就加。要加高精度,位数试了好多次,多了tle,少了re……不压位200应该在哪个oj都够了。

我的程序

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int l1,l2;
char s1[3010],s2[3010];
struct cbig{
    int num[200];
    int len;
}dp[3][3005];
vector<int> num[5];
int s[150];
void cop(cbig &a,cbig &b)
{
    for(int i=1;i<=b.len;i++)
    a.num[i]=b.num[i];
    a.len=b.len;
}
cbig add(cbig &a,cbig &b)
{
    cbig c;
    memset(&c,0,sizeof(c));
    int l=max(a.len,b.len);
    for(int i=1;i<=l;i++)
    {
        c.num[i]+=a.num[i]+b.num[i];
        c.num[i+1]=c.num[i]/10;
        c.num[i]%=10;
    }
    if(c.num[l+1]) l++;
    c.len=l;
    return c;
}
void print(cbig &a)
{
    for(int i=a.len;i>0;i--)
    cout<<a.num[i];
}
int main()
{
    cin>>l1>>l2;
    scanf("%s%s",s1+1,s2+1);
    for(int i=1;i<=l2;i++)
    {
        if(s2[i]=='A') s2[i]='T',num[3].push_back(i);
        else if(s2[i]=='C') s2[i]='G',num[2].push_back(i);
        else if(s2[i]=='T') s2[i]='A',num[0].push_back(i);
        else s2[i]='C',num[1].push_back(i);
    }
    s['T']=3,s['G']=2,s['C']=1,s['A']=0;
    dp[0][0].num[1]=1,dp[0][0].len=1;
    for(int i=1;i<=l1;i++)
    {
        int pre=i&1,now=s[s1[i]];
        for(int j=0;j<=l2;j++)
        cop(dp[pre][j],dp[pre^1][j]);
        for(int k,j=0;j<num[now].size();j++)
        {
            k=num[now][j];
            dp[pre][k]=add(dp[pre][k],dp[pre^1][k-1]);
        }
    }
    print(dp[l1&1][l2]);
    return 0;
}```