아버지 욕심

http://acm.bnu.edu.cn/v3/contest_show.php?cid=5772#problem/I
m 의 길이 가 n 인 DNA 서열 을 정 하고 DNA 서열 을 구하 여 모든 서열 의 총 차 이 를 최소 화하 고 출력 사전 서열 을 최소 화 합 니 다.
한 번 에 m 개의 문 자 를 보고 나타 난 횟수 가 가장 많은 것 을 욕심 내 며 사전 순서 가 작은 것 을 우선 합 니 다.
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define clr0(x) memset(x,0,sizeof(x))
#define clr1(x) memset(x,-1,sizeof(x))
typedef long long LL;

struct DNA
{
	int a,c,g,t;
}d[1005];
int main()
{
	int t,n,m,i,j,ans,max;
	char s[1005];
	RD(t);
	while(t--)
	{
	    RD2(n,m);
	    clr0(d);
		for(i=0;i<n;i++){
            scanf("%s",s);
            for(j=0;j<m;j++)
                if(s[j]=='A') d[j].a++;
                else if(s[j]=='C') d[j].c++;
		 		else if(s[j]=='G') d[j].g++;
                else d[j].t++;
		}
		for(ans=i=0;i<m;i++)
		{
			s[i]='A';max=d[i].a;
			if(d[i].c>max) s[i]='C',max=d[i].c;
			if(d[i].g>max) s[i]='G',max=d[i].g;
			if(d[i].t>max) s[i]='T',max=d[i].t;
			ans+=n-max;
		}
		s[m]=0;
		printf("%s
%d
",s,ans); } return 0; }

좋은 웹페이지 즐겨찾기