【POJ 1080】 Human Gene Functions

相似于最长公共子序列的做法

dp[i][j]表示 str1[i]相应str2[j]时的最大得分

转移方程为

dp[i][j]=max(dp[i-1][j-1]+score[str1[i]][str2[j]],

max(dp[i-1][j]+score[str1[i]][‘-‘],dp[i][j-1]+score[‘-‘][str2[j]]) )

注意初始化0下标就好

代码例如以下:

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int dp[101][101];

char a[102],b[102];

int sc['Z'+1]['Z'+1];

int main()

{

    int t,aa,bb,i,j;

    scanf("%d",&t);

    sc['A']['A'] = sc['C']['C'] = sc['G']['G'] = sc['T']['T'] = 5;

    sc['A']['C'] = sc['C']['A'] = sc['A']['T'] = sc['T']['A'] = sc['T']['-'] = -1;

    sc['G']['A'] = sc['A']['G'] = sc['C']['T'] = sc['T']['C'] = sc['G']['T'] = sc['T']['G'] = sc['G']['-'] = -2;

    sc['A']['-'] = sc['C']['G'] = sc['G']['C'] = -3;

    sc['C']['-'] = -4;

    while(t--)

    {

        scanf("%d %s %d %s",&aa,a+1,&bb,b+1);

        dp[0][0] = 0;

        for(i = 1; i <= bb; ++i) dp[0][i] = sc[b[i]]['-'] + dp[0][i-1];

        for(i = 1; i <= aa; ++i) dp[i][0] = sc[a[i]]['-'] + dp[i-1][0];

        for(i = 1; i <= aa; ++i)

        {

            for(j = 1; j <= bb; ++j)

            {

               dp[i][j] = max(dp[i-1][j-1] + sc[a[i]][b[j]],max(dp[i-1][j] + sc[a[i]]['-'],dp[i][j-1] + sc[b[j]]['-']));

            }

        }

        printf("%d\n",dp[aa][bb]);

    }

    return 0;

}