动态规划练习 9-白红宇

动态规划练习 9

阅读量：6170 次

发布时间：2019-06-21

本文共 2281 字，大约阅读时间需要 7 分钟。

题目：Human Gene Functions (POJ 1080)

链接：

#include 
#include 
#include 
 
using namespace std;
 
int score[256][256];
 
int get_score(char a, char b)
{
return score[(unsigned char)a][(unsigned char)b];
}
 
void set_score(char a, char b, int s)
{
score[(unsigned)a][(unsigned)b] = s;
score[(unsigned)b][(unsigned)a] = s;
}
 
// The recursion version.
int get_max_score(const string &a, size_t i, const string &b, size_t j)
{
if (i < a.size() && j < b.size())
{
int score = max(
get_score(a[i], '-') + get_max_score(a, i + 1, b, j),
get_score('-', b[j]) + get_max_score(a, i, b, j + 1));
 
return max(score, get_score(a[i], b[j]) + get_max_score(a, i + 1, b, j + 1));
}
else if (i < a.size())
{
return get_score(a[i], '-') + get_max_score(a, i + 1, b, j);
}
else if (j < b.size())
{
return get_score('-', b[j]) + get_max_score(a, i, b, j + 1);
}
 
return 0;
}
 
int main(int argc, char **argv)
{
set_score('A', 'A', 5);
set_score('A', 'C', -1);
set_score('A', 'G', -2);
set_score('A', 'T', -1);
set_score('A', '-', -3);
set_score('C', 'C', 5);
set_score('C', 'G', -3);
set_score('C', 'T', -2);
set_score('C', '-', -4);
set_score('G', 'G', 5);
set_score('G', 'T', -2);
set_score('G', '-', -2);
set_score('T', 'T', 5);
set_score('T', '-', -1);
 
int dp[101][101];
int n;
 
cin >> n;
 
while (n--)
{
int m;
string geneA, geneB;
 
memset(dp, 0, sizeof(dp));
 
cin >> m >> geneA;
cin >> m >> geneB;
 
if (geneA.size() > 100 || geneB.size() > 100)
{
continue;
}
 
// Recursion version.
// cout << get_max_score(geneA, 0, geneB, 0) << endl;
// dp[i][j] = max(
//      dp[i - 1][j - 1] + get_score(geneA[i], geneB[j]),
//      dp[i - 1][j] + get_score(geneA[i], '-'),
//      dp[i][j - 1] + get_score('-', geneB[j]));
for (size_t i = 1; i <= geneA.size(); ++i)
{
dp[i][0] = dp[i - 1][0] + get_score(geneA[i - 1], '-');
}
 
for (size_t j = 1; j <= geneB.size(); ++j)
{
dp[0][j] = dp[0][j - 1] + get_score('-', geneB[j - 1]);
}
 
for (size_t i = 1; i <= geneA.size(); ++i)
{
for (size_t j = 1; j <= geneB.size(); ++j)
{
dp[i][j] = max(
dp[i - 1][j] + get_score(geneA[i - 1], '-'),
dp[i][j - 1] + get_score('-', geneB[j - 1]));
dp[i][j] = max(
dp[i][j],
dp[i - 1][j - 1] + get_score(geneA[i - 1], geneB[j - 1]));
}
}
 
cout << dp[geneA.size()][geneB.size()] << endl;
}
 
return 0;
}