#include <iostream>
using namespace std;
int max(int a,int b,int c) 
{
	int d=(a > b ? a :b) > c ? (a > b ? a :b) : c;
	return d;
}
int table(char a, char b)
{
    int dna[5][5] =
    {
        { 5,-1,-2,-1,-3},
        { -1,5,-3,-2,-4},
        { -2,-3,5,-2,-2},
        { -1,-2,-2,5,-1},
        { -3,-4,-2,-1,0}
    };
	int m,n;
	if(a=='-') m=4;
    if(b=='-') n=4;
	if(a=='A') m=0;
	if(a=='C') m=1;
	if(a=='G') m=2;
	if(a=='T') m=3;
	if(b=='A') n=0;
	if(b=='C') n=1;
	if(b=='G') n=2;
	if(b=='T') n=3;
    return dna[m][n];
}
int main()
{
	int opt[102][102];
	int i,j,num1,num2,t,ma;
	char a[102],b[102];
	cin>>t;
	while(t--)
	{
		cin>>num1;
		cin>>a;
		cin>>num2;
		cin>>b;
		opt[0][0]=0;
		for(i=1;i<=num1;i++)
			opt[0][i] = opt[0][i-1]+table('-',a[i-1]);
	    for(i=1;i<=num2;i++)
			opt[i][0] = opt[i-1][0]+table('-',b[i-1]);
		if(num1>num2) ma=num1;
		else ma=num2;
	    for(i = 1; i <= num1; i++){
                for(j = 1; j <=num2; j++){
                        opt[i][j] = opt[i-1][j-1] + table(a[i-1],b[j-1]);
                        if(opt[i][j] < opt[i-1][j] + table(a[i-1],'-')){
                                opt[i][j] = opt[i-1][j] + table('-',a[i-1]);
                        }

                        if(opt[i][j] < opt[i][j-1] + table('-',b[i-1])){
                                opt[i][j] =opt[i][j-1] +table('-',b[i-1]);
                        }
                }
        }



        cout<<opt[num1][num2]<<endl;
	}
	return 0;
}

• Re:老大，你的DP方程看不懂啊~~~~ (0) yzhw 2009-04-26 16:24:54