UVA 1368 DNA Consensus String（共識字符串）問題詳解與解法

UVA 1368 DNA Consensus String（共識字符串）問題詳解與解法

給定m條長度為n的DNA序列（字符集{A,C,G,T}）。尋找一個長度n的字符串y，使其與所有m條序列的漢明距離之和最小。若多解，輸出字典序最小者。並輸出最小距離和（共識誤差）。

核心觀察

漢明距離逐位獨立。對第j列，選擇字符ch貢獻的距離為m - count[ch]（count[ch]為該列出現ch的次數）。為最小化總和，每列獨立選出現次數最多的字符；次數相同選字典序最小（A<C<G<T）。

算法流程

1. 讀入m, n及m條序列。
2. 對每列j=0..n-1：
   • 統計A,C,G,T計數cnt[4]。
   • 找最大計數對應字符（按A,C,G,T順序遍歷保證字典序最小）。
   • 輸出該字符，累加maxCnt到totalMax。
3. 共識誤差 = m*n - totalMax。

C++ 參考實現（AC代碼）

#include 
#include 
using namespace std;

char seq[50][1005];
int main() {
    int T; cin >> T;
    while (T--) {
        int m, n; cin >> m >> n;
        for (int i = 0; i < m; ++i) cin >> seq[i];
        int totalMax = 0;
        for (int j = 0; j < n; ++j) {
            int cnt[4] = {0}; // A,C,G,T
            for (int i = 0; i < m; ++i) {
                char c = seq[i][j];
                if (c == 'A') cnt[0]++;
                else if (c == 'C') cnt[1]++;
                else if (c == 'G') cnt[2]++;
                else if (c == 'T') cnt[3]++;
            }
            int best = 0;
            for (int k = 1; k < 4; ++k)
                if (cnt[k] > cnt[best]) best = k;
            // 字典序 A

關鍵點總結

逐位獨立決策：漢明距離可加性，將全局優化分解為n個獨立單列優化。
字典序處理：統計順序固定為A,C,G,T，cnt[k] > cnt[best]（嚴格大於）保證相等時保留先遇到的（字典序更小）。
複雜度：O(T * m * n)，m≤50, n≤1000極快。
誤差計算：總距離 = 總位數 - 最大匹配位數 = m*n - Σ maxCnt。

本題展示了貪心策略在獨立子問題上的最優性，是字符串統計類問題的經典入門。