题目：https://www.luogu.org/problemnew/show/P1140

分析：

本题一看就知道是一道动归，其实和字串距离非常的像，只不过多了题目规定的匹配相似度罢了。

匹配的相似度我们之间用一个二维数组读入即可

int shuzu[6][6]={{0,0,0,0,0,0},{0,5,-1,-2,-1,-3},{0,-1,5,-3,-2,-4},{0,-2,-3,5,-2,-2},{0,-1,-2,-2,5,-1},{0,-3,-4,-2,-1,0}};

PS:换行效果更佳。

然后要把字符串转化成刚才数组中的下标，便于读写

int start(char c) { if(c=='A')return 1; if(c=='C')return 2; if(c=='G')return 3; if(c=='T')return 4; }

然后直接在主函数中调用即可

之后就是调用问题

for(int i=0;i<n;i++) { a[i+1]=start(s1[i]); } for(int j=0;j<m;j++) { b[j+1]=start(s2[j]); }

其中s1，s2均为读入的字符串，我们把它们分别逐字符转化放入a，b数组。

然后由于有负值出现，我们需要把动归的核心方程初始化为一个极小的负数

for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { f[i][j]=-2147483647; } }

然后就是关键的动归核心部分了。

首先，看到数据范围：100

受到启发：二位数组开的起，再加上字串距离的引导，我们很容易想到$f[i][j]$可以表示第一个字符串的前i个字符与第二个字符串的前j个字符匹配的最大值。

状态想出来，那么方程如何转移呢？

根据可以加入空碱基，我们能想到

$f[i][j]=max(f[i][j],f[i-1][j]+shuzu[a[i]][5],f[i][j-1]+shuzu[b[j]][5],f[i-1][j-1]+shuzu[a[i]][b[i]]$ 分别是s1串的最后一个字符对应一个空字符，s2串的最后一个字符对应一个空字符，s1串个s2串的最后一个字符直接对应。

显而易见的，初始化f数组就是

for(int i=1;i<=n;i++)f[i][0]=f[i-1][0]+shuzu[a[i]][5]; for(int i=1;i<=m;i++)f[0][i]=f[0][i-1]+shuzu[b[i]][5];

然后把它们拼凑起来，就完工喽！

完结撒花~

转载于:https://www.cnblogs.com/vercont/p/10210069.html

相关资源：JAVA上百实例源码以及开源项目