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

    ACM-POJ EXP 166阅读 0评论

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


    大致题意

    题意就是给出一个主串,和一本字典,问最少在主串删除多少字母,可以使其匹配到字典的单词序列。

    PS:是匹配单词序列,而不是一个单词

    解题思路

    动态规划

    不多说,看程序

    主要是知道状态方程的含义

    dp[i]表示从message中第i个字符开始,到第L个字符(结尾处)这段区间所删除的字符数,初始化为dp[L]=0

    由于我的程序是从message尾部向头部检索匹配,所以是下面的状态方程:

    \small{ \begin{cases} dp[i]=dp[i+1]+1, \qquad \text{不能匹配时(最坏情况,删除最多字符)} \\\ dp[i]=min\\{dp[i], dp[pm]+(pm-i)-len\\}, \qquad \text{可以匹配时,取最优} \end{cases} }

    从程序可以看出,第i个位置到L所删除的字符数,总是先取最坏情况,只有可以匹配单词时才进入第二条方程进行状态优化更新。

    第一条方程不难理解,只要弄懂dp[i]的意义就能简单推导

    第二条方程难点在dp[pm]+(pm-i)-len

    从程序知道,pm是message的指针(其中i表示当前所匹配的单词在message中的起始位置),pd是字典的指针

    匹配的过程是

    当确认message第i位和某单词的首位吻合时,就开始逐字匹配,字符相同则两个指针同时向后移动一次,否则pd固定,pm移动。当因为pm>L跳出匹配时,说明匹配失败,dp[i]状态不变;当pd==单词长度时,单词匹配成功,进行dp[i]的状态优化

    显然,匹配成功时,pm-i代表匹配过程中,从位置i到pm的区间长度,再减去单词长度len,则得到从i到pm所删除的字符数(pm-i)-len。又dp[pm]表示从pm到L所删除的字符数(根据检索方向,dp[pm]的值在此前已经被作为最坏打算处理,因此并不是空值)

    从而dp[pm]+(pm-i)-len表示i到L删除的字符数,不难证明这个值一定比dp[i]相等或更优,因此取min赋值给dp[i]

    这是本题最难的地方

    最后输出dp[0]就可以了,dp[0]的意思相信大家都明白了

    转载请注明:EXP 技术分享博客 » POJ3267 – The Cow Lexicon

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

    表情

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

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