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

    ACM-POJ EXP 121阅读 0评论

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


    解题思路

    原序列S的逆序列为S’,则这道题目的关键在于:

    最少需要补充的字母数 = 原序列S的长度 — S和S’的最长公共子串长度

    这个公式我不证明,不难证

    剩下的就小意思了,最基础的LCS题。

    注意本题空间开销非常大,需要适当的处理手法


    先看看几种不同的申请空间方法的区别:

    1、静态数组 :开销大小为5001*5001的int是铁定超的.(据说用short int的话不会MLE,有兴趣的同学可以试试)

    2、动态数组 :单纯的申请动态数组是不能解决这个问题的,动态数组只能增加空间利用率,但是本题最恶劣的数组大小还是5001*5001,动态数组是不能改变这个事实的

    3、滚动数组 :这里重点讲一下滚动数组在这个题目中的应用.自己目前理解的应用滚动数组的目的就是减少空间开销.首先可以在纸上简单模拟一下DP的转移过程.确定好最少行数或者列数之后,重点就是在如何进行”滚动”以及如何用表达式控制这个滚动.

    对于本题,我用的是行数以0--1--0--1的滚动方式,滚动表达式为i%2和(i-1)%2 ,没错,就是强大的求余滚动O(∩_∩)O

    由于应用了滚动数组,那么空间开销就能够从5001*5001压缩到 2*5001 !!!

    哈哈,傻眼了吧(^o^)/~

    而且本题我为了稍微提高一点空间利用率,使用了 动态二维滚动数组,就是东邪(动态)西毒(滚动)的混合体O(∩_∩)O,这样做的目的,只是对测试数据库的数据抱有一点点希望:我相信它们不全都是5000的长度,所以我想能尽可能再节省一点列数….不过时间就惨不忍睹咯,1157ms….不过空间开销却由MLE跌落到谷底的280K(^o^)/~

    跪求传说中 300K 16ms代码………….


    顺便贴一下LCS的图解算法

    s1:2 5 7 9 3 1 2

    s2:3 5 3 2 8

    一. 使用二維陣列

    二. 記錄每一格的結果,是由哪一格而來

    1、陣列開頭均設為空

    2、S1[i]=S2[j]相同,dp[i][j]则继承左上方向dp[i-1][j-1]的值+1

    3、不相同dp[i][j]则继承 上方與左方中的最大數值

    最后整个二維陣列中最大的值,就是s1和s2的最长公共子串长度

    转载请注明:EXP 技术分享博客 » POJ1159 – Palindrome

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

    表情

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

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