Posted on 2008-03-15 16:38
superman 閱讀(338)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1027 C++ 00:00.01 892K */
2 #include <cstdio>
3 #include <cstring>
4 #include <iostream>
5
6 using namespace std;
7
8 int score(char a, char b)
9 {
10 if(a == b) return 5;
11 if(a == 'A')
12 {
13 if(b == 'C' || b == 'T')
14 return -1;
15 if(b == 'G') return -2;
16 if(b == ' ') return -3;
17 }
18 if(a == 'C')
19 {
20 if(b == 'A') return -1;
21 if(b == 'G') return -3;
22 if(b == 'T') return -2;
23 if(b == ' ') return -4;
24 }
25 if(a == 'G')
26 {
27 if(b == 'A' || b == 'T' || b == ' ')
28 return -2;
29 if(b == 'C') return -3;
30 }
31 if(a == 'T')
32 {
33 if(b == 'A' || b == ' ')
34 return -1;
35 if(b == 'C' || b == 'G')
36 return -2;
37 }
38 if(a == ' ')
39 {
40 if(b == 'A') return -3;
41 if(b == 'C') return -4;
42 if(b == 'G') return -2;
43 if(b == 'T') return -1;
44 }
45 }
46
47 int main()
48 {
49 int n, la, lb, opt[120][120];
50 char sa[120], sb[120];
51
52 scanf("%d", &n);
53 while(n--)
54 {
55 scanf("%d %s", &la, sa + 1);
56 scanf("%d %s", &lb, sb + 1);
57
58 opt[0][0] = 0;
59 for(int i = 1; i <= la; i++)
60 opt[i][0] = opt[i - 1][0] + score(sa[i], ' ');
61 for(int j = 1; j <= lb; j++)
62 opt[0][j] = opt[0][j - 1] + score(' ', sb[j]);
63
64 for(int i = 1; i <= la; i++)
65 for(int j = 1; j <= lb; j++)
66 {
67 opt[i][j] = opt[i - 1][j - 1] + score(sa[i], sb[j]);
68 opt[i][j] >?= opt[i][j - 1] + score(' ', sb[j]);
69 opt[i][j] >?= opt[i - 1][j] + score(sa[i], ' ');
70 }
71
72 printf("%d\n", opt[la][lb]);
73 }
74
75 return 0;
76 }
77