题解 P5484 【[JLOI2011]基因补全】

· · 题解

我的博客

题目传送门：P5484

思路：

此题考虑直接dp，设 f[i][j] 表示A串匹配了 i 个，B串匹配了 j 个的方案数。

想想怎么转移？

我们关注A串。当A串增添一个字符 a_i，即从 f[i-1][j] 转移到 f[i][j] 的时候。

假如 a_i != b_j，那么显然有 f[i][j]=f[i-1][j] 。

假如 a_i == b_j，那么所有的 f[i-1][j-1] 包含的串都可以在后面接上 a_i,b_i ，同样地，那么所有的 f[i-1][j] 包含的串，都可以把B串的最后一个去掉，然后再分别填上 a_i,b_i 。所以 f[i][j]=f[i-1][j-1]+f[i-1][j](when \ a_i == b_j)

我们想象到方案数巨多，并且没有取模，所以肯定要用高精。

此时又有一个问题，每个状态都要开一个二维数组，还要处理高精，容易MLE，怎么办呢？

我们容易想到到 i 可以用滚动数组优化（具体看我的代码里面qaq），然后我们就可以A一道省选题啦！

代码：(压8位高精)


#include<bits/stdc++.h>
#define lovelive 100000000
using namespace std;

int n,m,p=1,l;

char a1[2009],a2[2005];

struct aqours{
    int s[105],l;
    aqours(){l=1;}
}f[2][2005];

aqours operator + (aqours a,aqours b){//重载运算符 
    aqours c;
    c.l=max(a.l,b.l);
    memset(c.s,0,sizeof c.s);
    for(int i=1;i<=c.l;i++){
        c.s[i]+=a.s[i]+b.s[i];
        if(c.s[i]>=lovelive){
            c.s[i]-=lovelive;
            c.s[i+1]++;             //压8位高精qaq 
        }
    }
    if(c.s[c.l+1]) c.l++;
    return c;
}

bool chikatakami(char a,char b){//判断是否可以匹配 
    return 
    (a=='A'&&b=='T') ||
    (a=='C'&&b=='G') ||
    (a=='T'&&b=='A') ||
    (a=='G'&&b=='C');
}

void print(aqours a){
    cout<<a.s[a.l];
    for(int i=a.l-1;i;i--){
        printf("%08d",a.s[i]);
    }
} 

int main(){
    scanf("%d%d%s%s",&n,&m,a1+1,a2+1);
    f[0][0].s[1]=1;f[1][0].s[1]=1;
    for(int i=1;i<=n;i++,p^=1,l^=1)//滚动数组
        for(int j=1;j<=m;j++){
            f[p][j]=f[l][j];
            if(chikatakami(a1[i],a2[j])) f[p][j]=f[p][j]+f[l][j-1];//DP
        }
    print(f[l][m]);
    return 0;
}