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

題意：給你幾個字符串，找到一個字符串，使其到所有字符串的總Hamming的距離盡量小，Hamming就是字符不同的位置個數。如有多解輸出字典序最小的。和題目有關的就是序列只有 AGCT，，高中生物學過。。uva總是把題目說的天花亂墜。

方法：找每一列最多的那個。別怕麻煩。

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   

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;
	}
}