#include<fstream.h>ifstream fin("gene.in");
ofstream fout("gene.out");const int maxn=101;
const int d[5][5]={{5,-1,-2,-1,-3},
   {-1,5,-3,-2,-4},
   {-2,-3,5,-2,-2},
   {-1,-2,-2,5,-1},
   {-3,-4,-2,-1,0x7fff}};
char a[maxn],b[maxn];
int la,lb,n;void init()
{
char temp;
int i;
int num[256];
num['A']=0;
num['C']=1;
num['G']=2;
num['T']=3;
num['-']=4;
fin>>la;
fin.get(temp);
for (i=1;i<=la;i++)
{
fin.get(a[i]);
a[i]=num[a[i]];
}
fin>>lb;
fin.get(temp);
for (i=1;i<=lb;i++)
{
    fin.get(b[i]);
    b[i]=num[b[i]];
}
}void main()
{
init();
int f[maxn][maxn];
int i,j;
memset(f,0,sizeof(f));
f[0][0]=0;
for (i=1;i<=la;i++)
    f[i][0]=f[i-1][0]+d[a[i]][4];
for (i=1;i<=lb;i++)
    f[0][i]=f[0][i-1]+d[4][b[i]];
for (i=1;i<=lb;i++)
    for (j=1;j<=la;j++)
    {
int max=-0x7fff;
if (f[j-1][i-1]+d[a[j]][b[i]]>max)
   max=f[j-1][i-1]+d[a[j]][b[i]];
if (f[j-1][i]+d[a[j]][4]>max)
   max=f[j-1][i]+d[a[j]][4];
if (f[j][i-1]+d[4][b[i]]>max)
   max=f[j][i-1]+d[4][b[i]];
f[j][i]=max;
    }
fout<<f[la][lb]<<endl;
}

解决方案 »

  1.   

    上面那道题是一道noip2004模拟题的解答来着,题目如下:相似基因
    源程序名    GENE.??? (PAS,C,CPP)
    可执行文件名   GENE.EXE
    输入文件名   GENE.IN 
    输出文件名     GENE.OUT大家都知道,基因可以看作一个碱基对序列。它包含了4种核苷酸,简记作A,C,G,T。生物学家正致力于寻找人类基因的功能,以利用于诊断疾病和发明药物。
    在一个人类基因工作组的任务中,生物学家研究的是:两个基因的相似程度。因为这个研究对疾病的治疗有着非同寻常的作用。两个基因的相似度的计算方法如下:
    对于两个已知基因,例如AGTGATG和GTTAG,将它们的碱基互相对应。当然,中间可以加入一些空碱基-,例如:
    A G T G A T - G
    - G T - - T A G这样,两个基因之间的相似度就可以用碱基之间相似度的总和来描述,碱基之间的相似度如下表所示:
     
    那么相似度就是:(-3)+5+5+(-2)+(-3)+5+(-3)+5=9。因为两个基因的对应方法不唯一,例如又有:
    A G T G A T G
    - G T T A - G相似度为:(-3)+5+5+(-2)+5+(-1)+5=14。规定两个基因的相似度为所有对应方法中,相似度最大的那个。输入
    共两行。每行首先是一个整数,表示基因的长度;隔一个空格后是一个基因序列,序列中只含A,C,G,T四个字母。1<=序列的长度<=100。输出
    仅一行,即输入基因的相似度。样例
    GENE.IN
    7 AGTGATG
    5 GTTAGGENE.OUT
    14能帮我解答一下吗?用pascal语言,谢谢啊!