Human Gene Functions poj1080 dp

2019-11-08 01:03:50

字体：大中小

来源：转载

供稿：网友

题意

给定T对包含的ATGC的字符串以及不同字符匹配的权值，且规定可以用-代替任意字符，求每一对字符串的最大匹配值

Solution

嗯很容易想到f[i][j] $f[i][j]$ 表示a串匹配到i，b串匹配到j的最大值，那么有三种转移

i和j匹配i和-匹配j和-匹配

然后初值是个迷要-INF，预处理一下n个-匹配和m个-匹配的情况就好了

Code

#include <iostream>#include <string>#include <string.h>#define rep(i, st, ed) for (int i = st; i <= ed; i += 1)#define fill(x, t) memset(x, t, sizeof(x))#define N 111using namespace std;int f[N][N], map[N][N];inline int max(int x, int y){ return x>y?x:y;}int main(void){ ios::sync_with_stdio(false); map['A']['A'] = 5; map['A']['C'] = -1; map['A']['G'] = -2; map['A']['T'] = -1; map['A']['-'] = -3; map['C']['A'] = -1; map['C']['C'] = 5; map['C']['G'] = -3; map['C']['T'] = -2; map['C']['-'] = -4; map['G']['A'] = -2; map['G']['C'] = -3; map['G']['G'] = 5; map['G']['T'] = -2; map['G']['-'] = -2; map['T']['A'] = -1; map['T']['C'] = -2; map['T']['G'] = -2; map['T']['T'] = 5; map['T']['-'] = -1; map['-']['A'] = -3; map['-']['C'] = -4; map['-']['G'] = -2; map['-']['T'] = -1; map['-']['-'] = 0; int T; cin >> T; while (T --){ fill(f, -63); int n, m; string s, t; cin >> n >> s >> m >> t; f[0][0] = 0; rep(i, 1, n){ f[i][0] = f[i - 1][0] + map['-'][s[i - 1]]; } rep(i, 1, m){ f[0][i] = f[0][i - 1] + map['-'][t[i - 1]]; } rep(i, 1, n){ rep(j, 1, m){ f[i][j] = max(f[i][j], f[i - 1][j] + map['-'][s[i - 1]]); f[i][j] = max(f[i][j], f[i][j - 1] + map['-'][t[j - 1]]); f[i][j] = max(f[i][j], f[i - 1][j - 1] + map[s[i - 1]][t[j - 1]]); } } cout << f[n][m] << endl; } return 0;}

上一篇：Keyboard Row

下一篇：将对象存储在HTML5 localStorage中

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注