POJ 1080 Human Gene Functions(LCS变形)

POJ 1080 Human Gene Functions

题目大意

求两基因的相似度，可以在每个基因对中加入若干空格，每个字母与其他字母或自身和空格对应都有一个打分，则相似度就是最大的得分和

分析

LCS变形，我采用的是递归的写法 dp[i][j]表示第一串前i个字符，第二串前j个字符匹配所能得到的最大分数和。状态和状态的转移都类似于最长公共子序列问题（LCS）只是字符和字符匹配的分数不是固定的1而是以一个表的形式给出，处理起来比LCS稍微麻烦了一点。

代码

#include<cstdio> #include<iostream> #include<cmath> #include<cstdlib> #include<cstring> using namespace std; const int INF=999999; int n1,n2; char s1[105],s2[105];//下标从1开始 int dp[105][105];//dp[i][j]表示s1中以s1[i]字符结尾的字串于s2中s2[j]结尾的字串匹配得到的最大分数 int score[5][5]={ 5,-1,-2,-1,-3, -1,5,-3,-2,-4, -2,-3,5,-2,-2, -1,-2,-2,5,-1, -3,-4,-2,-1,0 }; int GetNum(char c) { if(c=='A')return 0; else if(c=='C')return 1; else if(c=='G')return 2; else if(c=='T')return 3; else return 4; } void Init() { for(int i=0;i<=100;i++) for(int j=0;j<=100;j++) dp[i][j]=-INF; } int Dp(int i,int j) { if(dp[i][j]!=-INF)return dp[i][j]; int ans=0; if(i==0)//边界条件 { for(int k=1;k<=j;k++) ans+=score[GetNum(s2[k])][4]; return dp[i][j]=ans; } else if(j==0) { for(int k=1;k<=i;k++) ans+=score[GetNum(s1[k])][4]; return dp[i][j]=ans; } ans=Dp(i-1,j-1)+score[GetNum(s1[i])][GetNum(s2[j])]; ans=max(ans,Dp(i-1,j)+score[GetNum(s1[i])][4]); ans=max(ans,Dp(i,j-1)+score[GetNum(s2[j])][4]); return dp[i][j]=ans; } int main() { int T; scanf("%d",&T); while(T--) { Init(); scanf("%d%s",&n1,s1); scanf("%d%s",&n2,s2); for(int i=n1-1;i>=0;i--)s1[i+1]=s1[i]; for(int i=n2-1;i>=0;i--)s2[i+1]=s2[i]; cout<<Dp(n1,n2)<<endl; } }