当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

POJ1080

发表于: 2012-12-12   作者:EmmaZhao   来源:转载   浏览次数:
poj
摘要: #include<iostream> #include<string> using namespace std; int value['T'+1]['T'+1]; int dp[101][101]; int max(int a,int b,int c) { int k = (a>b)?a:b; return (c>k)?c:k; }
#include<iostream>
#include<string>
using namespace std;
int value['T'+1]['T'+1];

int dp[101][101];
int max(int a,int b,int c)
{
	int k = (a>b)?a:b;
	return (c>k)?c:k;
}
int main(){
	value['A']['A'] = value['C']['C']=value['T']['T']=value['G']['G'] =5;
	value['A']['C'] = value['C']['A'] = -1;
	value['A']['G'] = value['G']['A'] = -2;
	value['A']['T'] = value['T']['A'] = -1;
	value['A']['-'] = value['-']['A'] = -3;
	value['C']['G'] = value['G']['C'] = -3;
	value['C']['T'] = value['T']['C'] =-2;
	value['C']['-'] = value['-']['C'] = -4;
	value['G']['T'] = value['T']['G'] = -2;
	value['G']['-'] = value['-']['G'] = -2;
	value['T']['-'] = value['-']['T'] = -1;
	int n,la,lb;
	string a,b;
	cin>>n;
	while(n--)
	{
		cin>>la>>a>>lb>>b;
		int i,j;
		dp[0][0] = 0;
		for(i = 1;i<=la;i++) dp[i][0] = dp[i-1][0] + value[a[i-1]]['-'];
		for(i = 1;i<=lb;i++ ) dp[0][i] = dp[0][i-1] +value[b[i-1]]['-'];
		for(i = 1;i<=la;i++)
		{
			for(j = 1;j<=lb;j++)
			{
				dp[i][j] = max(dp[i-1][j-1] + value[a[i-1]][b[j-1]],dp[i-1][j]+value[a[i-1]]['-'],dp[i][j-1]+value['-'][b[j-1]]);
			}
		}
		cout<<dp[la][lb]<<endl;
	}

}

POJ1080

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号