自动搬运

查看原文

来自洛谷，原作者为

	AquaRio 青鸟终将飞越那道彩虹的彼端， 所以我们也一定能够做到。

搬运于2025-08-24 22:11:15，当前版本为作者最后更新于2019-08-22 20:26:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我的博客

题目传送门：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;
}