记录编号	333279	评测结果	AAAAAAAAAA
题目名称	相似基因	最终得分	100
用户昵称	GROWL GOOD BOYส็	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2016-10-30 13:52:52	内存使用	0.42 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int maxn=100+20;

int N,M;

char s1[maxn],s2[maxn];

int dis[maxn][maxn],f[maxn][maxn];

void indis()
{
   dis['A']['A']=5;
   dis['A']['C']=-1;
   dis['A']['G']=-2;
   dis['A']['T']=-1;
   dis['A'][0]=-3;
   
   dis['C']['A']=-1;
   dis['C']['C']=5;
   dis['C']['G']=-3;
   dis['C']['T']=-2;
   dis['C'][0]=-4;
   
   
   dis['G']['A']=-2;
   dis['G']['C']=-3;
   dis['G']['G']=5;
   dis['G']['T']=-2;
   dis['G'][0]=-2;
   
   
   dis['T']['A']=-1;
   dis['T']['C']=-2;
   dis['T']['G']=-2;
   dis['T']['T']=5;
   dis['T'][0]=-1;
   
   dis[0]['A']=-3;
   dis[0]['C']=-4;
   dis[0]['G']=-2;
   dis[0]['T']=-1;  
}

int main()
{
    freopen("gene.in","r",stdin);
    freopen("gene.out","w",stdout);
    indis();
    scanf("%d%s",&N,s1+1);
    scanf("%d%s",&M,s2+1);
    memset(f,-0x7f/2,sizeof(f));
    f[0][0]=0;
    if(N<M)swap(N,M),swap(s1,s2);
    for(int i=1;i<=N;i++)f[i][0]=dis[s1[i]][0]+f[i-1][0];
    for(int i=1;i<=M;i++)f[0][i]=dis[s2[i]][0]+f[0][i-1];
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            f[i][j]=max(max(f[i-1][j-1]+dis[s1[i]][s2[j]],f[i-1][j]+dis[s1[i]][0]),f[i][j-1]+dis[0][s2[j]]);
        }
    }
    printf("%d",f[N][M]);
   
    fclose(stdin);
    fclose(stdout);
    return 0;
}