Human Gene Functions（poj 1080）

题目大意是：给定两组DNA序列，要你求出它们的最大相似度

每个字母与其他字母或自身和空格对应都有一个打分，求在这两个字符串中插入空格，让这两个字符串的匹配分数最大

/*

  思路是很好想的，设f[i][j]为A染色体前i个基因和B染色体前j个基因匹配的最大值

  第一次测样例WA了一把，f又没有赋最小值，今天第二次了，幸亏样例测出来了，不然又要WA一次。

*/

#include<cstdio>

#include<iostream>

#include<cstring>

#define N 110

using namespace std;

int a[N],b[N],f[N][N],n,m;

int v[][]={{,-,-,-,-},

             {-,,-,-,-},

             {-,-,,-,-},

             {-,-,-,,-},

             {-,-,-,-,}};

void work()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        char c;cin>>c;

        if(c=='A')a[i]=;

        if(c=='C')a[i]=;

        if(c=='G')a[i]=;

        if(c=='T')a[i]=;

    }

    scanf("%d",&m);

    for(int i=;i<=m;i++)

    {

        char c;cin>>c;

        if(c=='A')b[i]=;

        if(c=='C')b[i]=;

        if(c=='G')b[i]=;

        if(c=='T')b[i]=;

    }

    f[][]=;

    for(int i=;i<=n;i++)

      for(int j=;j<=m;j++)

      {

          if(i)f[i][j]=max(f[i][j],f[i-][j]+v[a[i]][]);

          if(j)f[i][j]=max(f[i][j],f[i][j-]+v[][b[j]]);

          if(i&&j)f[i][j]=max(f[i][j],f[i-][j-]+v[a[i]][b[j]]);

      }

    printf("%d\n",f[n][m]);

}

int main()

{

    freopen("jh.in","r",stdin);

    int T;scanf("%d",&T);

    while(T--)

    {

        memset(f,,sizeof(f));

        work();

    }

    return ;

}