UVa 1368 - DNA Consensus String

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給予一堆相同長度的 ATCG 構成的基因,找一段字典順序最小的基因,使得與給定的基因漢明碼距離(有多少位置不同)總和最小。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
3
5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA
6 10
ATGTTACCAT
AAGTTACGAT
AACAAAGCAA
AAGTTACCTT
AAGTTACCAA
TACTTACCAA

Sample Output

1
2
3
4
5
6
TAAGATAC
7
ACGTACGTAA
6
AAGTTACCAA
12

Solution

對於每一個位置,找到字符使用最多次的使用,這樣將可以將此位置的漢明碼距離縮到最短。

最後討論一下相同時所需要的最小字典順序,即可完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int testcase;
int n, m;
char DNA[64][1024];
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++)
scanf("%s", DNA[i]);
int hh = 0;
char ret[1024] = {}, cc[] = "ACGT";
for (int i = 0; i < m; i++) {
int cnt[4] = {}, mx = 0;
for (int j = 0; j < n; j++)
cnt[find(cc, cc+4, DNA[j][i]) - cc]++;
for (int j = 0; j < 4; j++) {
if (cnt[j] > cnt[mx])
mx = j;
}
ret[i] = cc[mx], hh += n - cnt[mx];
}
printf("%s\n%d\n", ret, hh);
}
return 0;
}