#include <stdio.h>

#define MAX 150
int             score[MAX][MAX], lena, lenb;
char            a[MAX], b[MAX];
int             dict[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, -127
                             };

int solve(void)
{
        int             i, j;

        score[0][0] = 0;
        for(i = 1; i <= lena; i++){
                score[i][0] = score[i-1][0] + dict[a[i-1]-'0'][4];
        }

        for(j = 1; j <= lenb; j++){
                score[0][j] = score[0][j-1] + dict[4][a[j-1]-'0'];
        }

        for(i = 1; i <= lena; i++){
                for(j = 1; j <= lenb; j++){
                        score[i][j] = score[i-1][j-1] + dict[a[i-1]-'0'][b[j-1]-'0'];
                        if(score[i][j] < score[i-1][j] + dict[a[i-1]-'0'][4]){
                                score[i][j] = score[i-1][j] + dict[a[i-1]-'0'][4];
                        }

                        if(score[i][j] < score[i][j-1] + dict[4][b[j-1]-'0']){
                                score[i][j] = score[i][j-1] + dict[4][b[j-1]-'0'];
                        }
                }
        }

        return score[lena][lenb];
}

int main(int argc, char **arv)
{
        int             i, cases;

        scanf("%d", &cases);
        getchar();

        while(cases--){
                scanf("%d ", &lena);
                for(i = 0; i < lena; i++){
                        scanf("%c", &a[i]);
                        switch(a[i]){
                                case 'A':
                                        a[i] = '0';
                                        break;
                                case 'C':
                                        a[i] = '1';
                                        break;
                                case 'G':
                                        a[i] = '2';
                                        break;
                                case 'T':
                                        a[i] = '3';
                                        break;
                        }
                }
                getchar();

                scanf("%d ", &lenb);
                for(i = 0; i < lenb; i++){
                        scanf("%c", &b[i]);
                        switch(b[i]){
                                case 'A':
                                        b[i] = '0';
                                        break;
                                case 'C':
                                        b[i] = '1';
                                        break;
                                case 'G':
                                        b[i] = '2';
                                        break;
                                case 'T':
                                        b[i] = '3';
                                        break;
                        }
                }
                getchar();
                printf("%d\n", solve());
        }
        return 0;
}

• Re:怎么老是WA啊，看不出哪里错了，麻烦高手指点一下！！！谢谢 (165) tiger2008 2008-05-25 23:00:04