链接:https://www.luogu.org/problem/P1140
思路:
设$f[i][j]$表示第一个串前$i$位与第二个串前$j$位匹配后的最大值。
可以将第$i$位与第$j$位直接匹配,或者分别用一个原字母匹配另一个空格。
代码:
#include <bits/stdc++.h> const int b[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} }; const int MAXN = 150; const int INF = 1 << 30; using namespace std; char s[MAXN], t[MAXN]; int n, m, f[MAXN][MAXN]; int change(char c) { if(c == 'A') return 1; if(c == 'C') return 2; if(c == 'G') return 3; if(c == 'T') return 4; } int main() { cin >> n >> (s + 1) >> m >> (t + 1); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) f[i][j] = -INF; } f[0][0] = 0; for(int i = 1; i <= n; i++) f[i][0] = f[i - 1][0] + b[change(s[i])][5]; for(int i = 1; i <= m; i++) f[0][i] = f[0][i - 1] + b[5][change(t[i])]; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { f[i][j] = max(f[i][j], f[i - 1][j] + b[change(s[i])][5]); f[i][j] = max(f[i][j], f[i][j - 1] + b[5][change(t[j])]); f[i][j] = max(f[i][j], f[i - 1][j - 1] + b[change(s[i])][change(t[j])]); } } cout << f[n][m] << endl; return 0; }