转载请注明出处：優YoU http://user.qzone.qq.com/289065406/blog/1300550378
LCS的变形而已
注意LCS的子串可以是离散的，不必连续，用动态规划
设dp[i][j]为取s1第i个字符，s2第j个字符时的最大分值
则决定dp为最优的情况有三种（score[][]为s1[i]和s2[j]两符号的分数）：
1、 s1取第i个字母，s2取“ - ”： dp[i-1][j]+score[ s1[i-1] ]['-'];
2、 s1取“ - ”，s2取第j个字母：dp[i][j-1]+score['-'][ s2[j-1] ];
3、 s1取第i个字母，s2取第j个字母：dp[i-1][j-1]+score[ s1[i-1] ][ s2[j-1] ];
即dp[i][j]=max( dp[i-1][j]+score[ s1[i-1] ]['-'],
dp[i][j-1]+score['-'][ s2[j-1] ],
dp[i-1][j-1]+score[ s1[i-1] ][ s2[j-1] ] );
注意初始化
不仅仅只有
dp[0][0] = 0
也不仅仅是
dp[0][0] = 0
dp[1][0] = score[ s1[i-1] ]['-']
dp[0][1] = score['-'][ s2[j-1] ]
必须全面考虑到所有情况，
当i=j=0时，dp[i][j]=0
当i=0时，dp[0,j] = dp[0][j-1] + score['-'][ s2[j-1] ]
当j=0时，dp[i,0] = dp[i-1][0] + score[ s1[i-1] ]['-']
1 //Memory Time
2 //300K 0MS
3
4 #include<iostream>
5 using namespace std;
6 const int inf=-5; //无穷小
7
8 int score['T'+1]['T'+1]; //积分表
9
10 void initial(void) //打表
11 {
12 score['A']['A']=5;
13 score['C']['C']=5;
14 score['G']['G']=5;
15 score['T']['T']=5;
16 score['-']['-']=inf;
17 score['A']['C']=score['C']['A']=-1;
18 score['A']['G']=score['G']['A']=-2;
19 score['A']['T']=score['T']['A']=-1;
20 score['A']['-']=score['-']['A']=-3;
21 score['C']['G']=score['G']['C']=-3;
22 score['C']['T']=score['T']['C']=-2;
23 score['C']['-']=score['-']['C']=-4;
24 score['G']['T']=score['T']['G']=-2;
25 score['G']['-']=score['-']['G']=-2;
26 score['T']['-']=score['-']['T']=-1;
27 return;
28 }
29
30 int max(int a,int b,int c)
31 {
32 int k=(b>c?b:c);
33 return a>k?a:k; //注意求三个数最大值时，a>b?a:(b>c?b:c)在C++中是错误的
34 } //b的值没有因为(b>c?b:c)而改变，必须把三个数拆开求最大值
35
36 int main(int i,int j)
37 {
38 initial();
39
40 int test;
41 cin>>test;
42 while(test--)
43 {
44 /*Input*/
45
46 int len1,len2;
47
48 cin>>len1;
49 char* s1=new char[len1+1];
50 cin>>s1;
51
52 cin>>len2;
53 char* s2=new char[len2+1];
54 cin>>s2;
55
56 int **dp=new int*[len1+1]; //申请动态二维数组，第一维
57 dp[0]=new int[len2+1];
58
59 /*Initial*/
60
61 dp[0][0]=0;
62 for(i=1;i<=len1;i++)
63 {
64 dp[i]=new int[len2+1]; //申请动态二维数组，第二维
65 dp[i][0]=dp[i-1][0]+score[ s1[i-1] ]['-']; //注意下标，dp数组是从1开始，s1和s2都是从0开始
66 }
67 for(j=1;j<=len2;j++)
68 dp[0][j]=dp[0][j-1]+score['-'][ s2[j-1] ];
69
70 /*Dp*/
71
72 for(i=1;i<=len1;i++)
73 for(j=1;j<=len2;j++)
74 {
75 int temp1=dp[i-1][j]+score[ s1[i-1] ]['-'];
76 int temp2=dp[i][j-1]+score['-'][ s2[j-1] ];
77 int temp3=dp[i-1][j-1]+score[ s1[i-1] ][ s2[j-1] ];
78 dp[i][j]=max(temp1,temp2,temp3);
79 }
80
81 cout<<dp[len1][len2]<<endl;
82
83 delete[] dp;
84 }
85 return 0;
86 }