problemb.cpp

给出不同的匹配的分数

/////////////////////////////////////////////////////////////////////////////////////////////
//					
//							ProblemB.cpp
//
//		算法描述：
//			给出不同的匹配的分数，求两个序列匹配的最大分数
//			递推关系： 
//	s[j] = max {s[i-1][j] + sc[i-1]['-'], s[j-1]+sc['-'][j-1],s[i-1][j-1]+sc[i-1][j-1]}
//
//////////////////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <queue>
using namespace std;

void init();
int maxs( int , int , int );

int sc[ 26][26];
int sum[2001][2001];
char str1[2001], str2[2001];

int main()
{
     init();
	 queue<int> qResult;
     int i ,j;
	 int tmp, tmp1, tmp2, tmp3;
	 int cas;
	 int l1, l2;
     cin>>cas;
     while(cas) //
     {
	    cas--;
        cin>>l1;
        cin>>str1;
        cin>>l2;
        cin>>str2;

        sum[0][0] = 0;  // 出始化基因相似性

        for(i=1; i<l1; i++) 
        {
		     tmp = sc['Q'][str2[i-1]];
             sum[0][i]=sum[0][i-1] + tmp;
        }
        for(i = 1;i<l2 ;i++)
        {
			tmp = sc[str1[i-1]]['Q'];
            sum[i][0] = sum[i-1][0] + tmp;
        }
        for(i = 1; i<= l1; i++) 
		{
			for ( j = 1 ; j<= l2 ; j ++ )
		    {
				tmp = sc [str1[i-1]]['Q'];
				tmp1 = sum[i-1][j] + tmp;
                   
				tmp = sc['Q'][str2[j-1]];
				tmp2 = sum[i][j-1] + tmp;
     
		        tmp3 = sum[i-1][j-1]+sc[str1 [i-1]][str2[j-1]];
                       
			   sum[i][j] = maxs(tmp1, tmp2, tmp3);
			}
		}
		qResult.push(sum[l1][l2]);
	}
	cout<<endl;
	while(!qResult.empty())
	{
		cout<<qResult.front()<<endl;
		qResult.pop();
	}
    return 0;
}

void init()              // 出始化基因表
{
	sc['A']['A'] = 5;
	sc['A']['C'] = -1;
	sc['A']['G'] = -2;
	sc['A']['T'] = -1;
	sc['A']['Q'] = -3;
    sc['C']['A'] = -1;
	sc['C']['C'] = 5;
	sc['C']['G'] = -3;
	sc['C']['T'] = -2;
	sc['C']['Q'] = -4;
    sc['G']['A'] = -2;
	sc['G']['C'] = -3;
	sc['G']['G'] = 5;
	sc['G']['T'] = -2;
	sc['G']['Q'] = -2;
    sc['T']['A'] = -1;
	sc['T']['C'] = -2;
	sc['T']['G'] = -2;
	sc['T']['T'] = 5;
	sc['T']['Q'] = -1;
    sc['Q']['A'] = -3;
	sc['Q']['C'] = -4;
	sc['Q']['G'] = -2;
	sc['Q']['T'] = -1;
}

int maxs(int tmp1, int tmp2, int tmp3) //取三者中大的数
{
     if(tmp1>=tmp2 && tmp1>= tmp3)
           return tmp1;
     if(tmp2>=tmp1 && tmp2>=tmp3)
           return tmp2;
     if(tmp3>=tmp1 && tmp3 >= tmp2)
           return tmp3;
}