第一題完全靠自己的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個(gè)基，b串j個(gè)基的最大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 閱讀(220)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ