欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

poj1080 Human Gene Functions (lcs变形)

程序员文章站 2022-07-12 08:58:56
...

题意:给定两个字符串 str1 和 str2 ,在两个串中都可以插入空格,使两个串的长度最后相等,然后开始匹配,怎样插入空格由匹配规则得到的值最大。

分析:LCS的变形,dp[i][j]表示str1[1...i]和str2[1...j]两个子串的最大匹配值。与lcs类似可以分3个方向对其进行状态转移:

由dp[i-1][j-1]转移过来,意味着str1[i]和str2[j]进行匹配,新增代价是str1[i]和str2[j]的匹配值。

由dp[i-1][j]转移过来,意味着str1[1...i-1]和str2[1...j]已经进行过匹配,str1[i]只能和空字符匹配,新增代价是str1[i]和空字符的匹配值。

③由dp[i][j-1]转移过来,与②类似。

得到状态转移方程:

dp[i][j] = max(dp[i - 1][j - 1] + match[str1[i]][str2[j]],
max(dp[i - 1][j] + match[str1[i]][' '], dp[i][j - 1] + match[str2[j]][' ']));


代码如下:

#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

int match[256][256];
int dp[110][110];
char str1[110], str2[110];
void init()
{
	match['A']['A'] = match['C']['C'] = match['G']['G'] = match['T']['T'] = 5;
	match['A']['C'] = match['C']['A'] = match['A']['T'] = match['T']['A'] = match['T'][' '] = match[' ']['T'] = -1;
	match['A']['G'] = match['G']['A'] = match['C']['T'] = match['T']['C'] = match['T']['G'] = match['G']['T'] = match[' ']['G'] = match['G'][' '] = -2;
	match['C']['G'] = match['G']['C'] = match[' ']['A'] = match['A'][' '] = -3;
	match['C'][' '] = match[' ']['C'] = -4;
}

int main()
{
	//fstream cin("test.txt");
	int k;
	cin >> k;
	init();
	while (k--)
	{
		memset(dp, 0, sizeof(dp));
		int len1, len2;
		
		cin >> len1 >> str1+1 >> len2 >> str2+1;
		dp[0][0] = 0;
		for (int i = 1; i <= len2; i++)
			dp[0][i] = dp[0][i - 1] + match[str2[i]][' '];	//注意这里一定要加上前一项						
		for (int i = 1; i <= len1; i++)						//因为计算的是前i个字符和空字符的匹配值
			dp[i][0] = dp[i - 1][0] + match[str1[i]][' '];
		for (int i = 1; i <= len1; i++)
			for (int j = 1; j <= len2; j++)
			{
				//dp[i][j] = dp[i - 1][j - 1] + match[str2[i - 1]][str1[j - 1]];
				dp[i][j] = max(dp[i - 1][j - 1] + match[str1[i]][str2[j]],
					max(dp[i - 1][j] + match[str1[i]][' '], dp[i][j - 1] + match[str2[j]][' ']));
			}
		cout << dp[len1][len2] << endl;
	}
	//system("pause");
	return 0;
}
需要注意的是我在做这题的时候WA了一次,看了别人的代码才发现是初始化的时候写错了,我想当然地把dp[i][0]和dp[0][j]的值初始化为str1[i]、str2[j]与空字符的匹配值,实际应该是str1[1...i]、str2[1...j]与空字符的匹配值。只能说自己对dp的理解还是不够到位吧。