POJ 1080 Human Gene Functions：帶權 LCS 的基因相似度計算

問題轉化

兩基因序列（A,C,G,T），插入間隙 '-' 使等長，按評分矩陣計分，求最大分值。
評分矩陣 5×5（含 '-'），'-' 與 '-' 不允許匹配（標 -∞）。

DP 定義

dp[i][j]：s1 前 i 字符、s2 前 j 字符對齊的最大分。
初始：dp[i][0] = dp[i-1][0] + score(s1[i], '-')，dp[0][j] 同理。
轉移：

dp[i][j] = max(
    dp[i-1][j]   + score(s1[i], '-'),   // s1 接 '-'
    dp[i][j-1]   + score('-', s2[j]),   // s2 接 '-'
    dp[i-1][j-1] + score(s1[i], s2[j])  // 字符對齊
);

字符映射

A→0, C→1, G→2, T→3, -→4，矩陣 mp[5][5] 直接查表。

複雜度

序列長 ≤ 100，O(L₁L₂) = 10⁴，極快。

代碼核心

int mp[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} };
int get(char c) { switch(c){ case 'A':return 0; case 'C':return 1; case 'G':return 2; case 'T':return 3; case '-':return 4; } }
for (int i=1;i<=len1;++i)
  for (int j=1;j<=len2;++j) {
    int t1 = dp[i-1][j] + mp[get(s1[i-1])][4];
    int t2 = dp[i][j-1] + mp[4][get(s2[j-1])];
    int t3 = dp[i-1][j-1] + mp[get(s1[i-1])][get(s2[j-1])];
    dp[i][j] = max(t1, max(t2, t3));
  }