解题报告

题目描述

链接： POJ1080

给定两个只包含 ATCG 四个字母的字符串（两串不等长），和一个字符串匹配得分表，要求匹配的最大得分

输入

第一行输入一个整数 T 代表用例个数
接下来有 2 * T 行，每一行首先输入一个字符代表 第一个串的长度 然后输入第一个串， 每两行为一个用例

输出

T 个整数，每一个代表最大匹配值，一个输出独占一行

解题思路

一开始拿到题完全不知道怎么做，后来参考了网上 思路，觉得可以与LCS类比一下：

LCS是指两个字符串最大公共子序列，也就是说 a[i]与b[j]需要相同才能匹配，但是这里可以堪称任意两个字符不管一不一样都可以匹配，而且字符还可以与'-'匹配，只是匹配结果（得分）可能有好有坏

dp[i][j]为 s1[0···i]与 s2[0···j]所组成的子串最大匹配值，那么dp[i][j]可以由以下三种情况：

1. dp[i][j] = dp[i-1][j-1] + (s1[i]与s2[j]匹配后的得分)

2. dp[i][j] = dp[i-1][j] + (s1[i]与‘-’匹配后的得分)

   即 s1[i]与‘-’匹配

3. dp[i][j] = dp[i][j-1] + (s2[j]与‘-’匹配后的得分)

   即 s2[j]与‘-’匹配

综上

dp[i][j] = 上述三种情况的最大值

代码

//
//  1080.cpp
//  POJ
//
//  Created by CaoKang on 2018/8/5.
//  Copyright © 2018 CaoKang. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int value[5][5] = {
    {5, -1, -2, -1, -3},
    {-1, 5, -3, -2, -4},
    {-2, -3, 5, -2, -2},
    {-1, -2, -2, 5, -1},
    {-3, -4, -2, -1, 0}
};

int change(char c){
    switch (c) {
        case 'A':
            return 0;
        case 'C':
            return 1;
        case 'G':
            return 2;
        case 'T':
            return 3;
        case '-':
            return 4;
    }
    return 1;
}

int main(){
    int T;
    cin >> T;
    while(T--){
        int leng1,leng2;
        string s1,s2;
        cin >> leng1>>s1>>leng2>>s2;
        s1 = "-" + s1;
        s2 = "-" + s2;
        vector<vector<int>> dp(leng1+1, vector<int>(leng2+1, 0));
        for(int i=1;i<=leng1;i++){
            dp[i][0] = dp[i-1][0] + value[change(s1[i])][change('-')];
        }
        for(int j=1;j<=leng2;j++){
            dp[0][j] = dp[0][j-1] + value[change('-')][change(s2[j])];
        }
        for(int i=1;i<=leng1;i++){
            for(int j=1;j<=leng2;j++){
                dp[i][j] = max(dp[i-1][j-1]+value[change(s1[i])][change(s2[j])], dp[i-1][j]+value[change(s1[i])][change('-')]);
                dp[i][j] = max(dp[i][j], dp[i][j-1] + value[change('-')][change(s2[j])]);
            }

        }
        cout<<dp[leng1][leng2]<<endl;
    }
}