Blog·Tanky WooABOUTRSS

HDU/HDOJ 1080 Human Gene Functions

28 Apr 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1080

经典的DP问题。

#include 
#include 
using namespace std;


int c[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, -10000
};

char s1[105], s2[105];
int s3[105], s4[105];
int a[105][105];
int n, len1, len2;

int fun(char m)
{
    if(m == 'A')
        return 0;
    else if(m == 'C')
        return 1;
    else if(m == 'G')
        return 2;
    else if(m == 'T')
        return 3;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> n;
    while(n--)
    {
        memset(a, 0, sizeof(a));
        cin >> len1;
        cin >> s1+1;
        cin >> len2;
        cin >> s2+1;

        for(int i=1; i<=len1; ++i)
            s3[i] =fun(s1[i]);
        for(int i=1; i<=len2; ++i)
            s4[i] =fun(s2[i]);
        //cout << s1+1 << " " << s2+1 << endl;

         a[0][0]=0;
         for(int i=1; i<=len1; ++i)
             a[i][0] = a[i-1][0] + c[s3[i]][4];
         for(int i=1; i<=len2; ++i)
             a[0][i] = a[0][i-1] + c[4][s4[i]];

         for(int i=1; i<=len1; ++i)
             for(int j=1; j<=len2; ++j)
             {
                 int k = a[i-1][j-1]+c[s3[i]][s4[j]];
                 if(k < a[i-1][j]+c[s3[i]][4])
                     k = a[i-1][j]+c[s3[i]][4];
                 if(k < a[i][j-1]+c[4][s4[j]])
                     k = a[i][j-1]+c[4][s4[j]];
                 a[i][j]=k;
             }

         cout << a[len1][len2] << endl;

        //for(int i=0; i<len1; ++i)
    }
}