平台:
UVa Online Judge
題號:
1368 - DNA Consensus String
題目連結:
q
題目說明:
输入m个长度均为n的DNA序列,求一个DNA序列,到所有序列的总Hamming距离尽量小。两个等长字符串的Hamming距离等于字符不同的位置个数,例如,ACGT和GCGA的Hamming距离为2(左数第1, 4个字符不同)。
输入整数m和n(4≤m≤50, 4≤n≤1000),以及m个长度为n的DNA序列(只包含字母A,C,G,T),输出到m个序列的Hamming距离和最小的DNA序列和对应的距离。如有多解,要求为字典序最小的解。
例如,对于下面5个DNA序列,最优解为TAAGATAC。
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
範例輸入:
3
5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA
6 10
ATGTTACCAT
AAGTTACGAT
AACAAAGCAA
AAGTTACCTT
AAGTTACCAA
TACTTACCAA
範例輸出:
TAAGATAC
7
ACGTACGTAA
6
AAGTTACCAA
12
解題方法:
矩阵中每列出现次数最多的就是最优解的单个。总的不同的,就是假设全部都错,m * n,然后减去相同最多的。
程式碼:
1 #include <cstdio> 2 #include <cstring> 3 4 const int MAXM = 55; 5 const int MAXN = 1024; 6 const int N = 4; 7 const char msg[] = "ACGT"; 8 9 char DNA[MAXM][MAXN] = { }; 10 char cols[MAXN][MAXM] = { }; 11 12 int findWhich(int cnt[], int& cntN, int m); 13 14 char findMost(char* str, int& cntN) { 15 int cnt[N] = { 0 }; 16 int m = strlen(str); 17 for (int i = 0; i < m; i++) { 18 switch (str[i]) { 19 case 'A': 20 cnt[0]++; 21 break; 22 case 'C': 23 cnt[1]++; 24 break; 25 case 'G': 26 cnt[2]++; 27 break; 28 case 'T': 29 cnt[3]++; 30 break; 31 default: 32 break; 33 } 34 } 35 return findWhich(cnt,cntN,m); 36 } 37 38 int findWhich(int cnt[], int& cntN, int m) { 39 int t = 0; 40 for (int i = 1; i < 4; i++) { 41 if (cnt[t] < cnt[i]) { 42 t = i; 43 } 44 //if (cnt[i] == 0) { 45 // cntN--; 46 //} 47 } 48 cntN -= cnt[t]; 49 return t; 50 } 51 52 int main() { 53 //freopen("in.txt", "r", stdin); 54 //freopen("out.txt", "w", stdout); 55 int T = 0; 56 scanf("%d", &T); 57 while (T--) { 58 memset(DNA, 0, sizeof(DNA)); 59 memset(cols, 0, sizeof(cols)); 60 int m = 0, n = 0; 61 scanf("%d%d", &m, &n); 62 int cntN = n * m; 63 getchar(); 64 for (int i = 0; i < m; i++) { 65 for (int j = 0; j < n; j++) { 66 DNA[i][j] = getchar(); 67 } 68 getchar(); 69 } 70 71 char str[MAXN] = { }; 72 for (int i = 0; i < n; i++) { 73 for (int j = 0; j < m; j++) { 74 cols[i][j] = DNA[j][i]; 75 } 76 str[i] = msg[findMost(cols[i],cntN)]; 77 } 78 printf("%s\n%d\n", str,cntN); 79 } 80 }