首页 > 代码库 > POJ1080 Human Gene Functions 动态规划 LCS的变形
POJ1080 Human Gene Functions 动态规划 LCS的变形
题意读了半年,唉,给你两串字符,然后长度不同,你可以用‘-’把它们补成相同长度,补在哪里取决于得分,它会给你一个得分表,问你最大得分
跟LCS很像的DP数组 dp[i][j]表示第一个字符串取第i个元素第二个字符串取第三个元素,然后再预处理一个得分表加上即可
得分表:
score['A']['A'] = score['C']['C'] = score['G']['G'] = score['T']['T'] = 5; score['A']['C'] = score['C']['A'] = -1; score['A']['G'] = score['G']['A'] = -2; score['A']['T'] = score['T']['A'] = -1; score['A']['-'] = score['-']['A'] = -3; score['C']['G'] = score['G']['C'] = -3; score['C']['T'] = score['T']['C'] = -2; score['C']['-'] = score['-']['C'] = -4; score['G']['T'] = score['T']['G'] = -2; score['G']['-'] = score['-']['G'] = -2; score['T']['-'] = score['-']['T'] = -1; score['-']['-'] = -inf;
那么DP方程就好推了:
dp[i][j] = :
dp[i-1][j] + score[s1[i-1]][‘-‘]或者
dp[i][j-1] + score[‘-‘][s2[j-1]]或者
dp[i-1][j-1] + score[s1[i-1]][s2[j-1]]或者
这三者之中取最大的
然后就是边界问题我给忘记了
不够细心,若单单是i==0或者j==0,边界问题就出现了,边界不可能为0的,所以还得处理一下边界
#include<iostream> #include<cstdio> #include<list> #include<algorithm> #include<cstring> #include<string> #include<queue> #include<stack> #include<map> #include<vector> #include<cmath> #include<memory.h> #include<set> #include<cctype> #define ll long long #define LL __int64 #define eps 1e-8 #define inf 0xfffffff //const LL INF = 1LL<<61; using namespace std; //vector<pair<int,int> > G; //typedef pair<int,int > P; //vector<pair<int,int> > ::iterator iter; // //map<ll,int >mp; //map<ll,int >::iterator p; const int N = 1000 + 5; int dp[N][N]; int score[200][200]; void init() { score['A']['A'] = score['C']['C'] = score['G']['G'] = score['T']['T'] = 5; score['A']['C'] = score['C']['A'] = -1; score['A']['G'] = score['G']['A'] = -2; score['A']['T'] = score['T']['A'] = -1; score['A']['-'] = score['-']['A'] = -3; score['C']['G'] = score['G']['C'] = -3; score['C']['T'] = score['T']['C'] = -2; score['C']['-'] = score['-']['C'] = -4; score['G']['T'] = score['T']['G'] = -2; score['G']['-'] = score['-']['G'] = -2; score['T']['-'] = score['-']['T'] = -1; score['-']['-'] = -inf; } int main () { init(); int t; char s1[N]; char s2[N]; scanf("%d",&t); while(t--) { int n,m; memset(dp,0,sizeof(dp)); scanf("%d %s",&n,s1); scanf("%d %s",&m,s2); for(int i=1;i<=n;i++) dp[i][0] = dp[i-1][0] + score[s1[i-1]]['-'];//边界处理 for(int j=1;j<=m;j++) dp[0][j] = dp[0][j-1] + score['-'][s2[j-1]];//边界处理 for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int t1 = dp[i-1][j] + score[s1[i-1]]['-']; int t2 = dp[i][j-1] + score['-'][s2[j-1]]; int t3 = dp[i-1][j-1] + score[s1[i-1]][s2[j-1]]; int maxn = max(t1,t2); dp[i][j] = max(maxn,t3); } } printf("%d\n",dp[n][m]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。