意甲冠军：该基因序列的两端相匹配，四种不同的核苷酸TCGA有不同的分值匹配。例如T—G比分是-2，它也可以被加入到空格，空洞格并且还具有一个相应的核苷酸匹配分值，求最大比分
分析：
在空气中的困难格的数量和位置不确定
二维dp，dp[i][j]表示序列a的前i段和序列b的前j段匹配时的最大分数。
接下来细致分析当i和j匹配的情况：1.a[i]与b[j]匹配；2.a[i]与b[j-1]。3.a[i]与b[j+1]。
所以方程：dp [i][j]= max(dp[i-1][j]+mat[i]['#'],dp[i][j-1]+mat['#'][j],dp[i-1][j-1]+mat[i][j])
代码：
#include<iostream>
#include<string>
#include<cstring>
#define INF 0x3f3f3f3f
using namespace std;
int t,n,m,dp[200][200];
string a,b;
int mat[200][200];
int max(int a,int b)
{
return a>b? a:b;
}
void f()
{
mat['A']['A']=5; mat['C']['C']=5; mat['G']['G']=5;
mat['T']['T']=5; mat['A']['C']=-1; mat['A']['G']=-2;
mat['A']['T']=-1; mat['A']['#']=-3; mat['C']['A']=-1;
mat['C']['G']=-3; mat['C']['T']=-2; mat['C']['#']=-4;
mat['G']['A']=-2; mat['G']['C']=-3; mat['G']['T']=-2;
mat['G']['#']=-2; mat['T']['A']=-1; mat['T']['C']=-2;
mat['T']['G']=-2; mat['T']['#']=-1; mat['#']['A']=-3;
mat['#']['C']=-4; mat['#']['G']=-2; mat['#']['T']=-1;
mat['#']['#']=-INF; }
int main()
{
f();
cin>>t;
while(t--){
cin>>n>>a;
cin>>m>>b;
dp[0][0]=0;
for(int i=1;i<=n;i++) dp[i][0]=dp[i-1][0]+mat[a[i-1]]['#'];
for(int i=1;i<=m;i++) dp[0][i]=dp[0][i-1]+mat['#'][b[i-1]];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=max(dp[i-1][j-1]+mat[a[i-1]][b[j-1]],
max(dp[i-1][j]+mat[a[i-1]]['#'],dp[i][j-1]+mat['#'][b[j-1]]));
}
}
cout<<dp[n][m]<<endl;
}
}
版权声明：本文博主原创文章，博客，未经同意不得转载。