據說經典DP，設opt[i][j]表示第二個基因序列的前i個基因和第一個基因序列的前j個匹配得到的最大值。
那么可以得到轉移方程啊opt[i][j] = max(a[i-1][j-1]+table[b[i-1]][a[i- ]], opt[i-1][j]+table['-'][a[j]], opt[i][j-1]+table[b[i]]['-']);
最后需要注意的就是邊界情況，即基因都匹配空的情況。
#include <stdio.h>
#include <string.h>
#define N 105
#define MAX(a, b) (a > b ? a : b)
int a[N][N];
char s1[N], s2[N];
int table[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, 0}};
inline int hash(char s)
{
if(s == 'A') return 0;
if(s == 'C') return 1;
if(s == 'G') return 2;
if(s == 'T') return 3;
if(s == '-') return 4;
}
int main()
{
int t, l1, l2;
scanf("%d", &t);
while(t--)
{
scanf("%d %s", &l1, &s1);
scanf("%d %s", &l2, &s2);
memset(a, 0, sizeof(a));
for(int i = 0; i < l1; i++)
{
a[0][i + 1] = a[0][i] + table[4][hash(s1[i])];
}
for(int i = 0; i < l2; i++)
{
a[i + 1][0] = a[i][0] + table[hash(s2[i])][4];
}
for(int i = 1; i <= l2; i++)
{
int x, y;
x = hash(s2[i - 1]);
for(int j = 1; j <= l1; j++)
{
y = hash(s1[j - 1]);
int t1, t2, t3;
t1 = a[i - 1][j - 1] + table[x][y];
t2 = a[i - 1][j] + table[x][4];
t3 = a[i][j - 1] + table[4][y];
a[i][j] = MAX(t1, MAX(t2, t3));
}
}
printf("%d\n", a[l2][l1]);
}
return 0;
}