UVALive 2324 Human Gene Functions（动态规划）

　　题意：求出将两个字符串改成一样长度所能形成最大的相似度。

　　思路：这个可以说是编辑距离的一个变形，编辑距离最终状态时要两个字符串完全一致，这个就是要求长度一样，而且这个只允许插入“—”这一个字符。模仿编辑距离定义状态，dp[i][j]表示将第一个字符串的前i个字符与第二个字符串的前j个字符变为相同长度所能形成的最大相似度。设两个字母的相似度为g[i][j];

　　那状态转移为 dp[i][j] = max( dp[i][j-1] + g[j][5], d[i-1][j] + g[i][5],dp[i-1][j-1] + g[i][j] ) 前两个代表插入“—”，后一个表示直接匹配。

　　注意：这个题我WA了两次，在定义初始状态dp[i][0] 和 dp[0][i]时，我忘记了累加消耗，而且还过了样例……后来自己举了一个例子才修正的。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
#define N 220
map<char,int> m;
int g[N][N];
void Init();///初始化得出相似度
char a[N],b[N];
int Solve(int lena,int lenb){
    int dp[N][N];
    char tmpa,tmpb;
    int numa,numb,sum;
    memset(dp,0,sizeof(dp));
    sum = 0;
    for(int i = 1;i <= lenb;i++){
        tmpb = b[i];
        numb = m[tmpb];
        sum += g[5][numb];///不要忘记消耗是累加的
        dp[0][i] = sum;
    }
    sum = 0;
    for(int i = 1;i <= lena;i++){
        tmpa = a[i];
        numa = m[tmpa];
        sum += g[numa][5];
        dp[i][0] = sum;
    }
    for(int i = 1;i <= lena;i++){
        for(int j = 1;j <= lenb;j++){
            tmpa = a[i],tmpb = b[j];
            numa = m[tmpa],numb = m[tmpb];
            dp[i][j] = max(dp[i-1][j]+g[numa][5],dp[i][j-1]+g[5][numb]);
            dp[i][j] = max(dp[i][j],dp[i-1][j-1]+g[numa][numb]);
        }
    }
    return dp[lena][lenb];
}
void Input(){
    int t,n,mm;
    scanf("%d",&t);
    while(t--){
        scanf("%d %s",&n,a+1);
        scanf("%d %s",&mm,b+1);
        printf("%d
",Solve(n,mm));
    }
}
int main(){
   // freopen("A.in.cpp","r",stdin);
    Init();
    Input();
    return 0;
}
void Init(){
    m.clear();
    m['A'] = 1;
    m['C'] = 2;
    m['G'] = 3;
    m['T'] = 4;
    memset(g,0,sizeof(g));
    for(int i = 1;i <= 4;i++){
        g[i][i] = 5;
    }
    g[1][5] = g[5][1] = -3;
    g[2][5] = g[5][2] = -4;
    g[3][5] = g[5][3] = -2;
    g[4][5] = g[5][4] = -1;
    g[1][2] = g[2][1] = g[1][4] = g[4][1] = -1;
    g[1][3] = g[3][1] = g[2][4] = g[4][2] = g[3][4] = g[4][3] = -2;
    g[2][3] = g[3][2] = -3;
}