1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
#include <stdlib.h>
#include <string.h>
#define MAXN 101
#define inf 0x0fffffff
int cost[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,-inf}};
int dp[MAXN][MAXN];
enum GENE{GENEA,GENEC,GENEG,GENET,SPACE};
int (int x,int y)
{
return x>y?x:y;
}
int Convert(char x)
{
switch(x)
{
case 'A':return GENEA;break;
case 'C':return GENEC;break;
case 'G':return GENEG;break;
case 'T':return GENET;break;
}
}
int DymanicSolve(int *a,int *b,int alen,int blen)
{
int i,j,k;
dp[0][0] = 0;
for (i = 1; i <= alen; i++)
dp[i][0] = dp[i-1][0]+cost[a[i]][SPACE];
for (j = 1; j <= blen; j++)
dp[0][j] = dp[0][j-1]+cost[SPACE][b[j]];
for (i = 1; i <= alen; i++)
for (j = 1; j <= blen; j++)
dp[i][j] = MAX(dp[i-1][j-1]+cost[a[i]][b[j]],MAX(dp[i-1][j]+cost[SPACE][a[i]],dp[i][j-1]+cb[j]][SPACE]));
return dp[alen][blen];
}
int main()
{
freopen("Sample Input.txt","r",stdin);
int SeqA[MAXN],Alen;
int SeqB[MAXN],Blen;
int T,i,j;
char c;
scanf("%d",&T);
while (T--)
{
scanf("%d",&Alen);
getchar();
for (i = 1; i <= Alen; i++)
{
c = getchar();
SeqA[i] = Convert(c);
}
getchar();
scanf("%d",&Blen);
getchar();
for (i = 1; i <= Blen; i++)
{
c = getchar();
SeqB[i] = Convert(c);
}
getchar();
printf("%dn",DymanicSolve(SeqA,SeqB,Alen,Blen));
}
getch();
return 0;
}
|
近期评论