#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX(a, b, c) (a > b ? a :b) > c ? (a > b ? a :b) : c

int ctoi(char a);
int value(char a, char b);

int main(void)
{
    int n, l1, l2, i, j, f[200][200], f1, f2, f3;
    char s1[100], s2[100];
    scanf("%d", &n);
    while (n--) {
        scanf("%d%s%d%s", &l1, s1 + 1, &l2, s2 + 1);
        memset(f, 0, sizeof(f));
        f[1][1] = 0;
        for (i = 2; i <= l1; i++)
            f[i][1] = f[i - 1][1] + value(s1[i], '-');
        for (j = 2; j <= l2; j++)
            f[1][j] = f[1][j - 1] + value('-', s2[j]);
        for (i = 1; i <= l1; i++)
            for (j = 1; j <= l2; j++) {
                    if (s1[i] == s2[j])
                        f[i][j] = f[i - 1][j - 1] + value(s1[i], s2[j]);
                    else {
                        f1 = f[i - 1][j] + value(s1[i], '-');
                        f2 = f[i][j - 1] + value('-', s2[j]);
                        f3 = f[i - 1][j - 1] + value(s1[i], s2[j]);
                        f[i][j] = MAX(f1, f2, f3);
                    }
            }
        printf("%d\n", f[l1][l2]);
    }
    return 0;
}

int value(char a, char b)
{
    int dna[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}
    };
    return dna[ctoi(a)][ctoi(b)];
}


int ctoi(char a)
{
    int b;
    if (a == 'A')   b = 0;
    if (a == 'C')   b = 1;
    if (a == 'G')   b = 2;
    if (a == 'T')   b = 3;
    if (a == '-')   b = 4;
    return b;
}

• Re:思路对啊，为什么总WA，谁给指点一下，谢谢 (1758) 20060810205 2009-03-05 20:17:15
  • Re:思路对啊，为什么总WA，谁给指点一下，谢谢 (16) mcluxun 2009-03-17 20:36:25