uva - 1368 - DNA Consensus String（字符串）

题意：给你几个字符串，找到一个字符串，使其到所有字符串的总Hamming的距离尽量小，Hamming就是字符不同的位置个数。如有多解输出字典序最小的。和题目有关的就是序列只有 AGCT，，高中生物学过。。uva总是把题目说的天花乱坠。

方法：找每一列最多的那个。别怕麻烦。

#include <iostream>  
#include <iomanip>  
#include <string>  
#include <cstring>  
#include <cstdio>  
#include <queue>  
#include <stack>  
#include <algorithm>  
#include <cmath>  

using namespace std;

char dna[50][1010], ans[1010];
int c[5], h;

void Input(int m, int n)
{
	int i = 0, j = 0;
	for (i = 0; i < m; i++)
		for (j = 0; j < n; j++)
			cin >> dna[i][j];
}

void Judge(int j, int i)
{
	switch(dna[j][i])
	{
	case ‘A‘: 
		c[0]++; break;
	case ‘C‘: 
		c[1]++; break;
	case ‘G‘:
		c[2]++; break;
	case ‘T‘:
		c[3]++; break;
	}
}

void Count_H(int m, int n)
{
	int i = 0, j = 0;
	for (i = 0; i < m; i++)
		for (j = 0; j < n; j++)
			if (dna[i][j] != ans[j])
				h++;
}

int main()  
{  
#ifdef Local    
	freopen("a.in", "r", stdin);    
#endif
	int t = 0;
	cin >> t;
	while (t--)
	{
		h = 0;
		memset(dna, ‘\0‘, sizeof(dna));
		memset(ans, ‘\0‘, sizeof(ans));
		int m, n, i = 0, j = 0;
		cin >> m >> n;
		Input(m, n);
		for (i = 0; i < n; i++)
		{
			memset(c, 0, sizeof(c));
			for (j = 0; j < m; j++)
				Judge(j, i);
			int max = 0, pos = 0;
			for (j = 0; j < 4; j++)
			{
				if (c[j] > max)
				{
					pos = j, max = c[j];
				}
			}
			switch(pos)
			{
			case 0:
				ans[i] = ‘A‘; break;
			case 1:
				ans[i] = ‘C‘; break;
			case 2:
				ans[i] = ‘G‘; break;
			case 3:
				ans[i] = ‘T‘; break;
			}
		}
		Count_H(m, n);
		cout << ans << endl;
		cout << h << endl;
	}
}

uva - 1368 - DNA Consensus String（字符串）

原文：http://blog.csdn.net/u013545222/article/details/19128419