Chinaunix首页 | 论坛 | 博客
  • 博客访问: 434630
  • 博文数量: 103
  • 博客积分: 5010
  • 博客等级: 大校
  • 技术积分: 971
  • 用 户 组: 普通用户
  • 注册时间: 2007-06-11 17:22
文章分类
文章存档

2008年(77)

2007年(26)

我的朋友

分类: C/C++

2008-06-01 19:08:32

求最长公共子序列的一个变形:

#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][b[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;
}

阅读(1799) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~