hdu 1080 Human Gene Functions 很霸气的DP

Human Gene Functions

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1307    Accepted Submission(s): 752

Problem Description
* denotes that a space-space match is not allowed. The score of the alignment above is (-3)+5+5+(-2)+(-3)+5+(-3)+5=9.

Of course, many other alignments are possible. One is shown below (a different number of spaces are inserted into different positions):

AGTGATG
-GTTA-G

This alignment gives a score of (-3)+5+5+(-2)+5+(-1) +5=14. So, this one is better than the previous one. As a matter of fact, this one is optimal since no other alignment can have a higher score. So, it is said that the similarity of the two genes is 14.
InputOutputSample InputSample Output

状态转移：

①dp[i][j]由dp[i-1][j]转移过来，代价是a[i-1]跟'-'匹配

②由dp[i][j-1]转移过来，代价是b[j-1]跟'-'匹配

③由dp[i-1][j-1]转移过来，代价是a[i-1]跟b[j-1]匹配

#include<stdio.h>#include<string.h>int max[500][500];int map[150][150];void match(){    map['A']['A']=5;map['A']['C']=-1;map['A']['G']=-2;map['A']['T']=-1;map['A']['-']=-3;    map['C']['A']=-1;map['C']['C']=5;map['C']['G']=-3;map['C']['T']=-2;map['C']['-']=-4;    map['G']['A']=-2;map['G']['C']=-3;map['G']['G']=5;map['G']['T']=-2;map['G']['-']=-2;    map['T']['A']=-1;map['T']['C']=-2;map['T']['G']=-2;map['T']['T']=5;map['T']['-']=-1;    map['-']['A']=-3;map['-']['C']=-4;map['-']['G']=-2;map['-']['T']=-1;//map['-']['-']=-3;}int main(){    int i,j,t,len1,len2;    char q1[500],q2[500];    match();    scanf("%d",&t);    while(t--)    {        scanf("%d %s",&len1,q1+1);        scanf("%d %s",&len2,q2+1);        memset(max,0,sizeof(max));        max[0][0]=0;        for(i=1;i<=len1;i++)              //max[i][0]=map[q1[i]]['-'];//哎 这里初始化搞错了 阿弥陀佛              max[i][0]=max[i-1][0]+map[q1[i]]['-'];        for(j=1;j<=len2;j++)        //    max[0][j]=map['-'][q2[j]];              max[0][j]=max[0][j-1]+map['-'][q2[j]];                for(i=1;i<=len1;i++)            for(j=1;j<=len2;j++)            {                max[i][j]=(max[i-1][j-1]+map[q1[i]][q2[j]])>(max[i-1][j]+map[q1[i]]['-'])?                    (max[i-1][j-1]+map[q1[i]][q2[j]]):(max[i-1][j]+map[q1[i]]['-']);                max[i][j]=max[i][j]>(max[i][j-1]+map['-'][q2[j]])?max[i][j]:(max[i][j-1]+map['-'][q2[j]]);            }            printf("%d\n",max[len1][len2]);    }    return 0;}