• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1080 – Human Gene Functions

    ACM-POJ EXP 130阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    解题思路

    LCS的变形而已

    注意LCS的子串可以是离散的,不必连续,用动态规划


    设dp[i][j]为取s1第i个字符,s2第j个字符时的最大分值

    则决定dp为最优的情况有三种(score[][]为s1[i]和s2[j]两符号的分数):

    1、 s1取第i个字母,s2取“ – ”: dp[i-1][j]+score[ s1[i-1] ]['-'];

    2、 s1取“ – ”,s2取第j个字母:dp[i][j-1]+score['-'][ s2[j-1] ];

    3、 s1取第i个字母,s2取第j个字母:dp[i-1][j-1]+score[ s1[i-1] ][ s2[j-1] ];

    即dp[i][j]=max( dp[i-1][j]+score[ s1[i-1] ]['-'],

    dp[i][j-1]+score['-'][ s2[j-1] ],

    dp[i-1][j-1]+score[ s1[i-1] ][ s2[j-1] ] );


    注意初始化

    不仅仅只有

    dp[0][0] = 0

    也不仅仅是

    dp[0][0] = 0

    dp[1][0] = score[ s1[i-1] ]['-']

    dp[0][1] = score['-'][ s2[j-1] ]

    必须全面考虑到所有情况,

    当i=j=0时,dp[i][j]=0

    当i=0时,dp[0,j] = dp[0][j-1] + score['-'][ s2[j-1] ]

    当j=0时,dp[i,0] = dp[i-1][0] + score[ s1[i-1] ]['-']

    转载请注明:EXP 技术分享博客 » POJ1080 – Human Gene Functions

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址