做题像在抄题解一样。。。

---

这道题说实话我肯定想不到，况且想出状态转移方程之后也不一定会写。

先分析题意：

设\(dp[i][j]\)为第一个串前\(i\)位，第二个串前\(j\)位的最大匹配值。

对每一次匹配，有三个决策：（想不到）

1. 第一个串的第\(i\)位空着，第二个串不空着。

2. 第一个串不空着，第二个串的第\(j\)位空着。

3. 不空。

注意：没有都空的决策，因为注定会有一个串全都要填。

所以状态转移方程就是：

\[dp[i][j] = max{dp[i - 1][j] + G[a[i]][0], dp[i][j - 1] + G[0][b[j]], dp[i - 1][j - 1] + G[a[i]][b[i]]}\]

边界情况也要注意。这里处理了所有的含有0的情况。

对第一维为0的，有：

\[dp[0][j] = dp[0][j - 1] + G[0][b[j]]\]

对第二维为0的，有：

\[dp[i][0] = dp[i - 1][0] + G[a[i]][0]\]

注意，答案可能为负，所以初始化为极小负数。

代码：

#include
    
     #include
     
      const int G[10][10] = {
    {0, -3, -4, -2, -1}, {-3, 5, -1, -2, -1}, {-4, -1, 5, -3, -2}, {-2, -2, -3, 5, -2}, {-1, -1, -2, -2, 5}};const int maxn = 105, INF = 19260817;int dp[maxn][maxn];bool vis[maxn][maxn];char ch1[maxn], ch2[maxn];int len1, len2;int change(char x){    if(x == 'A') return 1;    else if(x == 'C') return 2;    else if(x == 'G') return 3;    else if(x == 'T') return 4;}void init(){    for(int i = 1; i <= len1; i++) ch1[i] = change(ch1[i]);    for(int i = 1; i <= len2; i++) ch2[i] = change(ch2[i]);    for(int i = 1; i <= len1; i++) for(int j = 1; j <= len2; j++) dp[i][j] = -INF;    dp[0][0] = 0;    for(int i = 1; i <= len1; i++) dp[i][0] = dp[i - 1][0] + G[ch1[i]][0];    for(int j = 1; j <= len2; j++) dp[0][j] = dp[0][j - 1] + G[0][ch2[j]];}int solve(int i, int j){    if(vis[i][j]) return dp[i][j];    vis[i][j] = true;    if(i == 0) return dp[i][j];    if(j == 0) return dp[i][j];    dp[i][j] = std::max(dp[i][j], solve(i - 1, j) + G[ch1[i]][0]);    dp[i][j] = std::max(dp[i][j], solve(i, j - 1) + G[0][ch2[j]]);    dp[i][j] = std::max(dp[i][j], solve(i - 1, j - 1) + G[ch1[i]][ch2[j]]);    return dp[i][j];}int main(){    scanf("%d%s", &len1, ch1 + 1);    scanf("%d%s", &len2, ch2 + 1);    init();    printf("%d\n", solve(len1, len2));    return 0;}