正文

pku(1080)2005-09-08 04:16:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/ddtme/4493.html

分享到:

/*1080
观察题目给出的一个最优解:
AGTGATG
-GTTA-G
将其从某一处切开,如果左边部分的分值不是最大,那么将其进行调整,使其分值变大,
则整个解分值变大,与已知的最优矛盾。所以左边部分的分值必是最大。
同理,右边也是。可见满足最优子结构的性质。考虑使用DP:

设两个DNA序列分别为s1,s2,长度分别为len1,len2,score为分值表。
f[i,j]表示子串s1[1..i]和s2[1..j]的分值。考虑一个f[i,j],我们有:

  1.s1取第i个字母,s2取“-”:f[i-1,j] + score[s1[i],'-']

  2.s1取“-”,s2取第j个字母:f[i,j-1] + score['-',s2[j]]

  3.s1取第i个字母,s2取第j个字母:f[i-1,j-1] + score[s1[i],s2[j]]

  即f[i,j] = max(f[i-1,j] + score[s1[i],'-'], f[i,j-1] + score['-',s2[j]], f[i-1,j-1] + score[s1[i],s2[j]]);

然后考虑边界条件,这道题为i或j为0的情况。
当i=j=0时,即为f[0,0],这是在计算f[1,1]时用到的,根据f[1,1] = f[0,0] + score[s1[i], s2[j]],明显有f[0,0] = 0。
当i=0时,即为f[0,1..len2],有了f[0,0],可以用f[0,j] = f[0,j-1] + table['-',s2[j]]来计算。
当j=0时,即为f[1..len1,0],有了f[0,0],可以用f[i,0] = f[i-1,0] + table[s1[i],'-']来计算。

至于计算顺序,只要保证计算f[i,j]的时候,使用到的f[i-1,j],f[i,j-1],f[i-1,j-1]都计算出来了就行了。
所谓划分阶段也就是为了达到这个目的。这样我们使用一个二重循环就可以了。
*/
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;

#define MAX(a,b,c) (a>b?a:b)>c?(a>b?a:b):c

int ctoi(char a)
{
    int b;
    if(a=='A')        b = 0;
    if(a=='C')        b = 1;
    if(a=='G')        b = 2;
    if(a=='T')        b = 3;
    if(a=='-')        b = 4;
    return b;
}

int main()
{
    int t,j,k,m,n;
    int f1,f2,f3;
    int f[101][101];
    int arr[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}
    };
    string a,b;
    cin>>t;
    while(t--)
    {
        j = k = 0;
        memset(f,0,sizeof(f));
        cin>>m>>a;
        cin>>n>>b;
        for(j=0;j<=m;j++)
        {
            for(k=0;k<=n;k++)
            {
                if(j == 0 && k == 0)
                {
                    f[j][k] = 0;
                }
                else if(j==0)
                {
                    f[j][k] = f[j][k-1] + arr[ctoi('-')][ctoi(b[k-1])];
                }
                else if(k==0)
                {
                    f[j][k] = f[j-1][k] + arr[ctoi(a[j-1])][ctoi('-')];
                }
                else
                {
                    f1 = f[j-1][k]   + arr[ctoi(a[j-1])][ctoi( '-')];
                    f2 = f[j][k-1]   + arr[ctoi( '-')][ctoi(b[k-1])];
                    f3 = f[j-1][k-1] + arr[ctoi(a[j-1])][ctoi(b[k-1])];

                    f[j][k] = MAX(f1,f2,f3);
                
                }
            }
        }
        cout<<f[m][n]<<endl;
    }
    return 0;
}

阅读(4052) | 评论(0)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

暂无评论
您需要登录后才能评论,请 登录 或者 注册