/*
LeeMars的讲解如下:
观察题目给出的一个最优解:
AGTGATG
-GTTA-G
将其从某一处切开,如果左边部分的分值不是最大,那么将其进行调整,使其分值变大,则整个解分值变大,与已知的最优矛盾。所以左边部分的分值必是最大。同理,右边也是。可见满足最优子结构的性质。考虑使用DP:
设两个DNA序列分别为s1,s2,长度分别为len1,len2,score为分值表。f[i,j]表示子串s1[1..i]和s2[1..j]的分值。考虑一个f[i,j],我们有:
1.s1取第i个字母,s2取“-”:f[i-1,j] + score[s1[i],'-']
2.s1取“-”,s2取第j个字母:f[i,j-1] + score['-',s2[j]]
3.s1取第i个字母,s2取第j个字母:f[i-1,j-1] + score[s1[i],s2[j]]
即f[i,j] = max(f[i-1,j] + score[s1[i],'-'], f[i,j-1] + score['-',s2[j]], f[i-1,j-1] + score[s1[i],s2[j]]);
然后考虑边界条件,这道题为i或j为0的情况。
当i=j=0时,即为f[0,0],这是在计算f[1,1]时用到的,根据f[1,1] = f[0,0] + score[s1[i], s2[j]],明显有f[0,0] = 0。
当i=0时,即为f[0,1..len2],有了f[0,0],可以用f[0,j] = f[0,j-1] + table['-',s2[j]]来计算。
当j=0时,即为f[1..len1,0],有了f[0,0],可以用f[i,0] = f[i-1,0] + table[s1[i],'-']来计算。
至于计算顺序,只要保证计算f[i,j]的时候,使用到的f[i-1,j],f[i,j-1],f[i-1,j-1]都计算出来了就行了。所谓划分阶段也就是为了达到这个目的。这样我们使用一个二重循环就可以了。
*/
#include<iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
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, -100}
};
int dp[101][101];
int s1[101], s2[101];
int Max(int a, int b, int c)
{
if(a >= b && a >= c)
return a;
if(b >= a && b >= c)
return b;
if(c >= a && c >= b)
return c;
}
int main()
{
int n;
int i, j;
cin >> n;
while (n--)
{
int len1, len2;
string s;
cin >> len1 >> s;
for (i=0; i<s.size(); ++i)
{
if(s[i] == 'A') s1[i+1] = 0;
if(s[i] == 'C') s1[i+1] = 1;
if(s[i] == 'G') s1[i+1] = 2;
if(s[i] == 'T') s1[i+1] = 3;
}
cin >> len2 >> s;
for (i=0; i<s.size(); ++i)
{
if(s[i] == 'A') s2[i+1] = 0;
if(s[i] == 'C') s2[i+1] = 1;
if(s[i] == 'G') s2[i+1] = 2;
if(s[i] == 'T') s2[i+1] = 3;
}
memset(dp, 0, sizeof(dp));
dp[0][0] = 0;
for (i=1; i<=len1; ++i)
{
dp[i][0] = dp[i-1][0] + a[s1[i]][4];
}
for (j=1; j<=len2; ++j)
{
dp[0][j] = dp[0][j-1] + a[4][s2[j]];
}
for (i=1; i<=len1; ++i)
{
for (j=1; j<=len2; ++j)
{
int aa = dp[i-1][j-1] + a[s1[i]][s2[j]];
int bb = dp[i-1][j] + a[s1[i]][4];
int cc = dp[i][j-1] + a[4][s2[j]];
dp[i][j] = Max(aa, bb, cc);
}
}
cout << dp[len1][len2] << endl;
}
return 0;
}
LeeMars的讲解如下:
观察题目给出的一个最优解:
AGTGATG
-GTTA-G
将其从某一处切开,如果左边部分的分值不是最大,那么将其进行调整,使其分值变大,则整个解分值变大,与已知的最优矛盾。所以左边部分的分值必是最大。同理,右边也是。可见满足最优子结构的性质。考虑使用DP:
设两个DNA序列分别为s1,s2,长度分别为len1,len2,score为分值表。f[i,j]表示子串s1[1..i]和s2[1..j]的分值。考虑一个f[i,j],我们有:
1.s1取第i个字母,s2取“-”:f[i-1,j] + score[s1[i],'-']
2.s1取“-”,s2取第j个字母:f[i,j-1] + score['-',s2[j]]
3.s1取第i个字母,s2取第j个字母:f[i-1,j-1] + score[s1[i],s2[j]]
即f[i,j] = max(f[i-1,j] + score[s1[i],'-'], f[i,j-1] + score['-',s2[j]], f[i-1,j-1] + score[s1[i],s2[j]]);
然后考虑边界条件,这道题为i或j为0的情况。
当i=j=0时,即为f[0,0],这是在计算f[1,1]时用到的,根据f[1,1] = f[0,0] + score[s1[i], s2[j]],明显有f[0,0] = 0。
当i=0时,即为f[0,1..len2],有了f[0,0],可以用f[0,j] = f[0,j-1] + table['-',s2[j]]来计算。
当j=0时,即为f[1..len1,0],有了f[0,0],可以用f[i,0] = f[i-1,0] + table[s1[i],'-']来计算。
至于计算顺序,只要保证计算f[i,j]的时候,使用到的f[i-1,j],f[i,j-1],f[i-1,j-1]都计算出来了就行了。所谓划分阶段也就是为了达到这个目的。这样我们使用一个二重循环就可以了。
*/
#include<iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
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, -100}
};
int dp[101][101];
int s1[101], s2[101];
int Max(int a, int b, int c)
{
if(a >= b && a >= c)
return a;
if(b >= a && b >= c)
return b;
if(c >= a && c >= b)
return c;
}
int main()
{
int n;
int i, j;
cin >> n;
while (n--)
{
int len1, len2;
string s;
cin >> len1 >> s;
for (i=0; i<s.size(); ++i)
{
if(s[i] == 'A') s1[i+1] = 0;
if(s[i] == 'C') s1[i+1] = 1;
if(s[i] == 'G') s1[i+1] = 2;
if(s[i] == 'T') s1[i+1] = 3;
}
cin >> len2 >> s;
for (i=0; i<s.size(); ++i)
{
if(s[i] == 'A') s2[i+1] = 0;
if(s[i] == 'C') s2[i+1] = 1;
if(s[i] == 'G') s2[i+1] = 2;
if(s[i] == 'T') s2[i+1] = 3;
}
memset(dp, 0, sizeof(dp));
dp[0][0] = 0;
for (i=1; i<=len1; ++i)
{
dp[i][0] = dp[i-1][0] + a[s1[i]][4];
}
for (j=1; j<=len2; ++j)
{
dp[0][j] = dp[0][j-1] + a[4][s2[j]];
}
for (i=1; i<=len1; ++i)
{
for (j=1; j<=len2; ++j)
{
int aa = dp[i-1][j-1] + a[s1[i]][s2[j]];
int bb = dp[i-1][j] + a[s1[i]][4];
int cc = dp[i][j-1] + a[4][s2[j]];
dp[i][j] = Max(aa, bb, cc);
}
}
cout << dp[len1][len2] << endl;
}
return 0;
}