POJ1080 Human Gene Functions(LCS)

题目链接。

分析：

和 LCS 差不多。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>

using namespace std;

const int maxn = 200;

int G[][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 dp[maxn][maxn];

void trans(char *s, int n) {
    for(int i=0; i<n; i++) {
        switch(s[i]) {
        case 'A': s[i] = 0; break;
        case 'C': s[i] = 1; break;
        case 'G': s[i] = 2; break;
        case 'T': s[i] = 3; break;
        case '-': s[i] = 4; break;
        }
    }
}

int main(){
    int T, n, m;
  //  freopen("my.txt", "r", stdin);
    char s1[maxn], s2[maxn];

    scanf("%d", &T);

    while(T--) {
        scanf("%d%s%d%s", &n, s1, &m, s2);
        trans(s1, n); trans(s2, m);

        dp[0][0] = 0;
        for(int i=1; i<=m; i++) dp[i][0] = G[s2[i-1]][4] + dp[i-1][0];

        for(int i=1; i<=n; i++) dp[0][i] = G[s1[i-1]][4] + dp[0][i-1];

        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                int u = s2[i-1], v = s1[j-1];

                dp[i][j] = dp[i-1][j-1] + G[u][v];
                dp[i][j] = max(dp[i][j], dp[i-1][j]+G[u][4]);
                dp[i][j] = max(dp[i][j], dp[i][j-1]+G[v][4]);
            }
        }

        printf("%d
", dp[m][n]);
    }

    return 0;
}