posts - 100,  comments - 15,  trackbacks - 0
第一题完全靠自己的DP,一遍AC高兴...

 1#include<iostream>
 2using namespace std;
 3#define MAX 100
 4
 5int table['T'+1]['T'+1];    //scoring matrix
 6int score[MAX+1][MAX+1];    //score[i][j]表示a串有i个基,b串j个基的最大score
 7char a[MAX+1];  //string a
 8char b[MAX+1];  //string b
 9int la;  //length of a
10int lb;  //length of b
11
12void init()
13{
14    table['A']['A']=5;
15    table['A']['C']=-1;
16    table['A']['G']=-2;
17    table['A']['T']=-1;
18    table['A']['-']=-3;
19
20    table['C']['A']=-1;
21    table['C']['C']=5;
22    table['C']['G']=-3;
23    table['C']['T']=-2;
24    table['C']['-']=-4;
25
26    table['G']['A']=-2;
27    table['G']['C']=-3;
28    table['G']['G']=5;
29    table['G']['T']=-2;
30    table['G']['-']=-2
31        ;
32    table['T']['A']=-1;
33    table['T']['C']=-2;
34    table['T']['G']=-2;
35    table['T']['T']=5;
36    table['T']['-']=-1;
37
38    table['-']['A']=-3;
39    table['-']['C']=-4;
40    table['-']['G']=-2;
41    table['-']['T']=-1;
42}

43void dp()
44{
45    int i,j;
46    score[0][0]=0;
47    for(i=1;i<=la;i++)
48        score[i][0]=score[i-1][0]+table[a[i]]['-'];
49    for(i=1;i<=lb;i++)
50        score[0][i]=score[0][i-1]+table['-'][b[i]];
51    for(i=1;i<=la;i++)
52        for(j=1;j<=lb;j++)
53            score[i][j]=max(score[i-1][j-1]+table[a[i]][b[j]],max(score[i][j-1]+table['-'][b[j]],score[i-1][j]+table[a[i]]['-']));
54}

55
56
57int main()
58{
59    int T;
60    scanf("%d",&T);
61    init();
62    while(T--)
63    {
64        memset(a,0,sizeof(a));
65        memset(b,0,sizeof(b));
66        scanf("%d",&la);
67        scanf("%s",a+1);
68        scanf("%d",&lb);
69        scanf("%s",b+1);
70        dp();
71        printf("%d\n",score[la][lb]);
72    }

73    return 0;
74}

75

posted on 2009-05-02 16:21 wyiu 阅读(207) 评论(0)  编辑 收藏 引用 所属分类: POJ

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理