|
|
思路：
由于上下都可以加空格，這個有點崩潰。
但后來發現還是可以用動態規劃做的。
假設輸入的字符串分別為 A，B
f[i][j] = { 從 A[i] 和 B[j] 開始匹配，所能達到的最大值 }
假設 A[i] = G，B[j] = C
那么現在的情況就是
Gxxxxx
Cxxxxx
狀態轉移為
=> f[i + 1][j] + table(A[i], '-')
G...
-C..
=> f[i][j + 1] + table(B[j], '-')
-G..
C...
=> f[i + 1][j + 1] + table(A[i], B[j])
G...
C...
可以用滾動數組。
所以這樣就解決了，覺得很神奇。
 #include <stdio.h>
int N, M, f[2][256], *pre, *cur;
char A[256], B[256], map[256];
  int tbl[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 void swap(int **a, int **b)
{
 int *t = *a;
*a = *b;
*b = t;
}
inline int max(int a, int b)
{
return a > b ? a : b;
}
inline int min(int a, int b)
{
return a < b ? a : b;
}
inline int dif(char a, char b)
{
return tbl[map[a]][map[b]];
}
int main()
{
int t, i, j;
freopen("e:\\test\\in.txt", "r", stdin);
map['A'] = 0;
map['C'] = 1;
map['G'] = 2;
map['T'] = 3;
map['-'] = 4;
scanf("%d", &t);
while (t--) {
scanf("%d%s%d%s", &N, &A[1], &M, &B[1]);
pre = &f[0][0];
cur = &f[1][0];
cur[0] = 0;
for (i = 1; i <= M; i++)
cur[i] = dif(B[i], '-') + cur[i - 1];
for (i = 1; i <= N; i++) {
swap(&pre, &cur);
cur[0] = dif(A[i], '-') + pre[0];
for (j = 1; j <= M; j++) {
cur[j] = dif(A[i], B[j]) + pre[j - 1];
cur[j] = max(cur[j], dif(A[i], '-') + pre[j]);
cur[j] = max(cur[j], dif(B[j], '-') + cur[j - 1]);
 }
}
printf("%d\n", cur[M]);
}
}
|