HDU/HDOJ 1080 Human Gene Functions

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

经典的DP问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <algorithm>
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)
    }
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDU/HDOJ 1080 Human Gene Functions》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注