UVA1368 UVALive3602 ZOJ3132 DNA Consensus String【贪心】-白红宇

UVA1368 UVALive3602 ZOJ3132 DNA Consensus String【贪心】

阅读量：6307 次

发布时间：2019-06-22

本文共 1290 字，大约阅读时间需要 4 分钟。

Regionals 2006 >> Asia - Seoul

问题链接：。

问题简述：给定m个长度为n的DNA序列，求一个DNA序列，使其到所有这些序列的总hamming距离尽量小，如果有多个解，输出字典顺序的最小解。

问题分析：

每个DNA序列的长度相同，对每个DNA序列的每一位DNA码进行统计，选取出现次数最多的码，那么这一位的hamming距离最小。依次类推，每一位都选取出现次数最多的码，那么这样的DNA序列到n个给定的DNA序列的总hamming距离就会最小。考虑这是一个典型的可以用贪心法解决的例子。

程序说明：

程序中，为了计算方便，先使用map将DNA码“ACGT”映射为整数0、1、2和3，这个映射是按字典顺序的。统计计算并且得到计算结果后再将整数0、1、2和3其映射为相应的DNA码“ACGT”。这样做可以简化程序逻辑，不用写许多条件语句了。

AC的C++语言程序如下：

/* UVA1368 UVALive3602 ZOJ3132 DNA Consensus String */#include 
    
     #include 
     #include 
      
       #define MAXN 1000int dnacount[MAXN][4];using namespace std;int main(){    int t, m, n, ans, i, j;    map
       
         dnamap;    char dna[] = "ACGT", c;    char result[MAXN+1];    dnamap['A'] = 0;    dnamap['C'] = 1;    dnamap['G'] = 2;    dnamap['T'] = 3;    scanf("%d", &t);    while(t--) {        scanf("%d%d", &m, &n);        getchar();        memset(dnacount, 0, sizeof(dnacount));        for(i=0; i
        
          maxval) {                    maxval = dnacount[i][j];                    maxindex = j;                }            ans -= maxval;            result[i] = dna[maxindex];        }        result[n] = '\0';        printf("%s\n", result);        printf("%d\n", ans);    }    return 0;}

转载于:https://www.cnblogs.com/tigerisland/p/7564515.html

你可能感兴趣的文章