LA 3602 DNA Consensus String （暴力枚举）

题意：给定m个长度为n的DNA序列，求一个最短的DNA序列，使得总Hamming距离最小。

Hamming距离等于字符不同的位置个数。

析：看到这个题，我的第一感觉是算时间复杂度，好小，没事，完全可以暴力，只要对每个串的同一个位置，

都选出现最多的，如果有一样的选ASIIC码小的（因为要求字典序小）。然后记录最字符和Hamming距离即可。

代码如下：

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <queue>

#include <vector>

using namespace std;

const int maxn = 1000 + 10;

char s[55][maxn];

char ans[maxn];

int main(){

    int n, T, m, d, mm;  cin >> T;

    while(T--){

        scanf("%d %d", &m, &n);

        for(int i = 0; i < m; ++i)

            scanf("%s", s[i]);

        d = 0;

        for(int i = 0; i < n; ++i){

            int cnta = 0, cntc = 0, cntg = 0, cntt = 0;

            mm = 0;

            for(int j = 0; j < m; ++j){

                if('A' == s[j][i])  ++cnta;

                else if('C' == s[j][i])  ++cntc;

                else if('G' == s[j][i])  ++cntg;

                else if('T' == s[j][i])  ++cntt;

            }

            mm = max(mm, cnta);  mm = max(mm, cntc);//查找谁最多多

            mm = max(mm, cntg);  mm = max(mm, cntt);

            if(mm == cnta){   ans[i] = 'A';  d += cntc; d += cntg;  d += cntt; }//不同位置加和

            else if(mm == cntc){   ans[i] = 'C';  d += cnta; d += cntg;  d += cntt; }

            else if(mm == cntg){   ans[i] = 'G';  d += cntc; d += cnta;  d += cntt; }

            else if(mm == cntt){   ans[i] = 'T';  d += cntc; d += cntg;  d += cnta; }

        }

        ans[n] = '\0';//加结束符

        printf("%s\n%d\n", ans, d);

    }

    return 0;

}