POJ 1080

#include <iostream>
#include <string>

#define MAXN 110

using namespace std;

int _m[MAXN][MAXN];

int max(int a,int b,int c);

int cmp(char a,char b);

int main()
{
    //freopen("acm.acm","r",stdin);
    int test;
    string s_1;
    string s_2;
    int k;
    int i;
    int j;

    cin>>test;
    while(test --)
    {
        cin>>k;
        cin>>s_1;
        cin>>k;
        cin>>s_2;
        _m[0][0] = 0;
//        _m[1][0] = 0;
//        _m[0][1] = 0;
        for(i = 0; i < s_2.length(); ++ i)
        {
            _m[0][i+1] = _m[0][i] + cmp(‘ ‘,s_2[i]);
        }

        for(i = 0; i < s_1.length(); ++ i)
        {
            _m[i+1][0] = _m[i][0] + cmp(s_1[i],‘ ‘);
        }

    
        for(i = 0; i < s_1.length(); ++ i)
        {
            for(j = 0; j < s_2.length(); ++ j)
            {
                if(s_1[i] == s_2[j])
                {
                    _m[i+1][j+1] = 5 + _m[i][j];
                }
                else 
                {
                    _m[i+1][j+1] = max(cmp(s_1[i],‘ ‘) + _m[i][j+1],cmp(‘ ‘,s_2[j])+_m[i+1][j],cmp(s_1[i],s_2[j])+_m[i][j]);
                }
            }
        }
        cout<<_m[s_1.length()][s_2.length()]<<endl;
    }
}
int max(int a,int b);
int max(int a,int b,int c)
{
    if(a > max(b,c))
    {
        return a;
    }
    return max(b,c);
}

int max(int a,int b)
{
    if(a > b)
        return a;
    return b;
}

int cmp(char a,char b)
{
    if((a == ‘A‘ && b == ‘C‘) ||( a == ‘C‘ && b == ‘A‘))
    {
        return -1;
    }
    else if((a == ‘A‘ && b == ‘T‘) || (a == ‘T‘ && b == ‘A‘))
    {
        return -1;
    }
    else if((a == ‘A‘ && b == ‘G‘) || (a == ‘G‘ && b == ‘A‘))
    {
        return -2;
    }
    else if((a == ‘C‘ && b == ‘G‘) || (a == ‘G‘ && b== ‘C‘))
    {
        return -3;
    }
    else if((a == ‘C‘ && b == ‘T‘) || (a == ‘T‘ && b == ‘C‘))
    {
        return -2;
    }
    else if((a == ‘G‘ && b == ‘T‘) || (a == ‘T‘ && b == ‘G‘))
    {
        return -2;
    }
    else if( (a == ‘ ‘ && b == ‘A‘) || (a == ‘A‘ && b == ‘ ‘))
    {
        return -3;
    }
    else if((a == ‘ ‘ && b == ‘T‘) || (a == ‘T‘ && b == ‘ ‘))
    {
        return -1;
    }
    else if((a == ‘ ‘ && b == ‘C‘) || (a == ‘C‘ && b == ‘ ‘) )
    {
        return -4;
    }
    else if( (a == ‘ ‘ && b == ‘G‘) || (a == ‘G‘ && b == ‘ ‘) )
    {
        return -2;
    }
}