[solution][Dynamic Programming][Bitint]JLOI2011 基因补全

【题目】

戳这里

【题意】

给定两个序列,求短的序列在长的序列里出现的次数(可以不连续)。

【思路】

DP+高精。
设短序列S1,长序列S2.
表示S1前i个字符组成的序列在S2前j个字符组成的序列中出现的次数。
则有:


初始化:.

【代码】

/**************************************************************
    Problem: 2764
    User: wyfcyx
    Language: C++
    Result: Accepted
    Time:440 ms
    Memory:1216 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
const int mo = 100000000;
struct Bignum
{
    int d[25] , l;
    Bignum()
    {
        memset(d , 0 , sizeof(d));
        l = 0;
    }
    void clear()
    {
        memset(d , 0 , sizeof(d));
        l = 0;
    }
    void operator = (const int x)
    {
        d[l++] = x;
    }
    void operator += (const Bignum &b)
    {
        l = l > b.l ? l : b.l;
        for(register int i = 0 ; i < l ; ++i)
        {
            d[i] += b.d[i];
            if (d[i] >= mo)
            {
                d[i + 1] += d[i] / mo;
                d[i] %= mo;
            }
        }
        if (d[l]) l++;
    }
    void output()
    {
        printf("%d" , d[l - 1]);
        for(register int i = l - 2 ; i >= 0 ; --i)
            printf("%08d" , d[i]);
    }
};
const int N = 2001;
Bignum dp[2][N];
char s1[N] , s2[N];
int main()
{
    int n , m;
    scanf("%d%d" , &n , &m);
    scanf("%s%s" , s2 + 1, s1 + 1);
    register int i , j;
    for(i = 1 ; i <= m ; ++i)
    {
        if (s1[i] == 'A') s1[i] = 'T';
        else if (s1[i] == 'T') s1[i] = 'A';
        else if (s1[i] == 'C') s1[i] = 'G';
        else if (s1[i] == 'G') s1[i] = 'C';
    }
    for(j = 0 ; j <= n ; ++j)
        dp[0][j] =1;
    int now = 1;
    for(i = 1 ; i <= m ; ++i)
    {
        for(j = 0 ; j <= n ; ++j)
            dp[now][j].clear();
        for(j = 1 ; j <= n ; ++j)
        {
            dp[now][j] = dp[now][j - 1];
            if (s1[i] == s2[j])
                dp[now][j] += dp[now ^ 1][j - 1];
        }
        now ^= 1;
    }
    dp[now^1][n].output();
    return 0;
}
comments powered by Disqus