【题目链接】
点击打开链接【思路要点】
补档博客，无题解。【代码】
#include<bits/stdc++.h> using namespace std; #define MAXN 3005 #define INF 1e9 template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } char s[MAXN], t[MAXN]; int cost[5][5]; int n, m, A, B; int dp[MAXN][MAXN][3]; int index(char x) { if (x == 'A') return 0; if (x == 'T') return 1; if (x == 'G') return 2; return 3; } void chkmax(int &x, int y) { x = max(x, y); } int main() { scanf("\n%s", s + 1); n = strlen(s + 1); for (int i = 1; i <= n; i++) s[i] = index(s[i]); scanf("\n%s", t + 1); m = strlen(t + 1); for (int i = 1; i <= m; i++) t[i] = index(t[i]); for (int i = 0; i <= 3; i++) for (int j = 0; j <= 3; j++) read(cost[i][j]); read(A), read(B); for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) for (int k = 0; k <= 2; k++) dp[i][j][k] = -INF; dp[0][0][0] = 0; //0 : None; 1 : Upper; 2 : Lower. for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) { chkmax(dp[i + 1][j + 1][0], dp[i][j][0] + cost[s[i + 1]][t[j + 1]]); chkmax(dp[i][j + 1][1], dp[i][j][0] - A); chkmax(dp[i + 1][j][2], dp[i][j][0] - A); chkmax(dp[i + 1][j + 1][0], dp[i][j][1] + cost[s[i + 1]][t[j + 1]]); chkmax(dp[i][j + 1][1], dp[i][j][1] - B); chkmax(dp[i + 1][j][2], dp[i][j][1] - A); chkmax(dp[i + 1][j + 1][0], dp[i][j][2] + cost[s[i + 1]][t[j + 1]]); chkmax(dp[i][j + 1][1], dp[i][j][2] - A); chkmax(dp[i + 1][j][2], dp[i][j][2] - B); } int ans = max(dp[n][m][0], dp[n][m][1]); ans = max(ans, dp[n][m][2]); cout << ans << endl; return 0; }