首页 > 代码库 > POJ 1080 Human Gene Functions(动态规划)

POJ 1080 Human Gene Functions(动态规划)

2024-07-04 20:47:04   232人阅读

一开始用的DFS，无限TLE，贴丑代码

//version 1 TLE
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAX_INT 2147483647
#define MAXN 105

using namespace std;

int Map[5][5] = {
				{0,-3,-4,-2,-1},
				{-3,5,-1,-2,-1},
				{-4,-1,5,-3,-2},
				{-2,-2,-3,5,-2},
				{-1,-1,-2,-2,5},
				};
int seq1[MAXN],seq2[MAXN],Max,n1,n2;

int ref(char c)
{
	switch (c)
	{
		case ‘A‘:
			return 1;
		case ‘C‘:
			return 2;
		case ‘G‘:
			return 3;
		case ‘T‘:
			return 4;
	}
}

void dfs(int id1,int id2,int sum)
{
	if(id2 <= n2 + 1)
	{
		if(id2 == n2 + 1)
		{
			for(int i = id1;i <= n1;i ++)
				sum += Map[seq1[i]][0];
			Max = max(Max,sum);
			return ;
		}
		int limi = n1 - n2 + id2,tsum = sum;
		for(int i = id1;i <= limi;i ++)
		{
			if(i > id1)
				tsum += Map[seq1[i-1]][0];
			dfs(i + 1 , id2 + 1 , tsum + Map[seq1[i]][seq2[id2]]);
		}
	}
}

int main()
{
	freopen("./1080.in" , "r" , stdin);
	int T,i,j;
	char c;
	cin>>T;
	while(T --)
	{
		scanf("%d%c",&n1,&c);
		for(i = 1;i <= n1;i ++)
		{
			scanf("%c",&c);
			seq1[i] = ref(c);
		}
		scanf("%d%c",&n2,&c);
		for(i = 1;i <= n2;i ++)
		{
			scanf("%c",&c);
			seq2[i] = ref(c);
		}
		if(n1 < n2)
		{
			for(int i = 1;i <= n1;i ++)
				swap(seq1[i] , seq2[i]);
			for(int i = n1 + 1;i <= n2;i ++)
				seq1[i] = seq2[i];
			swap(n1 , n2);
		}
		Max = -MAX_INT;
		dfs(1,1,0);
		cout<<Max<<endl;
	}
	return 0;
}

之后冥思苦想了好久，两个序列，开始没有想到变形的LCS（最长公共子序列），只是试着写状态转移方程，最后就写成了那个dp[i][j] = max(dp[i-1][j-1] ````,dp[i-1][j]`````,dp[i][j-1]```)的样子，这时一看才明白这是LCS思想，但是一开始确实是瞎写的，可能碰巧了吧=。=，最后注意这种情况:dp[0][x]，当一个序列之前都用0补上的话，在循环过程中是没办法得到结果的，只能预先处理，切记！

/*
poj   1080
268K	0MS	
*/
#include<cstdio>
#include<cstring>
#include<iostream>

#define MAXN 105
#define MAX_INT 2147483647

using namespace std;

int Map[5][5] = {
				{0,-3,-4,-2,-1},
				{-3,5,-1,-2,-1},
				{-4,-1,5,-3,-2},
				{-2,-2,-3,5,-2},
				{-1,-1,-2,-2,5},
				};
int seq1[MAXN],seq2[MAXN],dp[MAXN][MAXN],n1,n2;

int ref(char c)
{
	switch (c)
	{
		case ‘A‘:
			return 1;
		case ‘C‘:
			return 2;
		case ‘G‘:
			return 3;
		case ‘T‘:
			return 4;
	}
}

int calc()
{
	memset(dp , 0 , sizeof(dp));
	for(int i = 1;i <= n1;i ++)
		dp[i][0] = dp[i-1][0] + Map[seq1[i]][0];
	for(int i = 1;i <= n2;i ++)
		dp[0][i] = dp[0][i-1] + Map[0][seq2[i]];
	for(int i = 1;i <= n1;i ++)
		for(int j = 1;j <= n2;j ++)
			dp[i][j] = max(dp[i-1][j-1] + Map[seq1[i]][seq2[j]] ,
				max(dp[i-1][j] + Map[seq1[i]][0] , dp[i][j-1] + Map[0][seq2[j]]) );
	return dp[n1][n2];
}

int main()
{
	int T,i,j;
	char c;
	cin>>T;
	while(T --)
	{
		scanf("%d%c",&n1,&c);
		for(i = 1;i <= n1;i ++)
		{
			scanf("%c",&c);
			seq1[i] = ref(c);
		}
		scanf("%d%c",&n2,&c);
		for(i = 1;i <= n2;i ++)
		{
			scanf("%c",&c);
			seq2[i] = ref(c);
		}
		cout<<calc()<<endl;
	}
	return 0;
}


联系
我们