Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我也来贴个代码,写个dp写的蛋碎了

Posted by TSERROF at 2012-11-07 16:28:34 on Problem 1080
#include<iostream>
#include <string>
#include <cstring>
using namespace std;
int map[200][200],dp[200][200];
int max(int a,int b,int c){ if(a<b)a=b;if(a<c)a=c;return a;}
int main()
{
	map['A']['C']=map['C']['A']=-1,map['A']['G']=map['G']['A']=-2,map['A']['T']=map['T']['A']=-1,map['C']['G']=map['G']['C']=-3,map['C']['T']=map['T']['C']=-2,map['T']['G']=map['G']['T']=-2,map['A']['-']=map['-']['A']=-3,map['C']['-']=map['-']['C']=-4,map['G']['-']=map['-']['G']=-2,map['T']['-']=map['-']['T']=-1,map['A']['A']=map['C']['C']=map['T']['T']=map['G']['G']=5,map['-']['-']=0;
	int T,n1,n2;
	cin>>T;
	while(T--)
	{
		string s1,s2,t;
		cin>>n1>>s1>>n2>>s2;
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n1;++i)dp[i][0]=dp[i-1][0]+map[s1[i-1]]['-'];
		for(int i=1;i<=n2;++i)dp[0][i]=dp[0][i-1]+map['-'][s2[i-1]];
		for(int i=1;i<=n1;++i)
			for(int j=1;j<=n2;++j)
			{
				dp[i][j]=max(dp[i-1][j-1]+map[s1[i-1]][s2[j-1]],dp[i-1][j]+map[s1[i-1]]['-'],dp[i][j-1]+map[s2[j-1]]['-']);
			}
		cout<<dp[n1][n2]<<endl;
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator