POJ 1080 Human Gene Functions(dp)

题意：给定两个字符串，求它们对齐匹配的最大值

要求：可以两个字符匹配，也可以一个字符和‘-’匹配，

但是不能两个‘-’匹配，例如：

AGTGATG

GTTAG

这两个字符串可以看成是

AGTGATG

-GTTA-G

也可以看成是

AGTGAT-G

-GT--TAG

分析：这是一个变形的最长公共子序列,最优解:

1.取字符i-1和j-1的时候dp[i][j]=dp[i-1][j-1]+a[s1[i-1]][s2[j-1]];
2.取字符i-1,不取j-1的时候dp[i][j]=dp[i-1][j]+a[s1[i-1]]['-'];
3.取字符j-1,不取i-1的时候dp[i][j]=dp[i][j-1]+a['-'][s2[j-1]];

而dp[i][j]取这三个值的最大值就可以了

当然初始化的时候dp[0][0]=0;
但是因为每个字符都要和一个字符对齐，当然不包括'-'和'-'两个字符对齐
所以当dp[0][i]的时候就代表s2[i-1]与'-'对齐，

所以dp[0][j]=dp[0][j-1]+a['-'][s2[j-1]];
同理dp[i][0]=dp[i-1][0]+a[s1[i-1]]['-'];

 1 #include<stdio.h>
 2 char s1[110],s2[110];
 3 int dp[110][110];
 4 int n1,n2;
 5 int a[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,0};
 6 int max(int a,int b,int c)
 7 {
 8     int maxn=a;
 9     if(b>maxn)
10         maxn=b;
11     if(c>maxn)
12         maxn=c;
13     return maxn;
14 }
15 int get(char ch)
16 {
17     if(ch=='A')
18         return 0;
19     if(ch=='C')
20         return 1;
21     if(ch=='G')
22         return 2;
23     if(ch=='T')
24         return 3;
25     if(ch=='-')
26         return 4;
27 }
28 void dpdp()
29 {
30     dp[0][0]=0;
31     int x,y,z;
32     int i,j;
33     for(i=1; i<=n1; i++)
34         dp[i][0]=dp[i-1][0]+a[get(s1[i-1])][get('-')];
35     for(j=1; j<=n2; j++)
36         dp[0][j]=dp[0][j-1]+a[get('-')][get(s2[j-1])];
37     for(i=1; i<=n1; i++)
38     {
39         for(j=1; j<=n2; j++)
40         {
41             x=dp[i-1][j-1]+a[get(s1[i-1])][get(s2[j-1])];
42             y=dp[i-1][j]+a[get(s1[i-1])][get('-')];
43             z=dp[i][j-1]+a[get('-')][get(s2[j-1])];
44             dp[i][j]=max(x,y,z);
45         }
46     }
47     return ;
48 }
49 int main()
50 {
51     int t;
52     scanf("%d",&t);
53     while(t--)
54     {
55         scanf("%d%s%d%s",&n1,s1,&n2,s2);
56         dpdp();
57         printf("%d
",dp[n1][n2]);
58     }
59     return 0;
60 }