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

    ACM-POJ EXP 220阅读 0评论

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


    大致题意

    2011 POJ暑假集训题Problem E,POJ上有中文版

    解题思路

    DFS+剪枝

    POJ2362 的强化版,重点在于剪枝

    令InitLen为所求的最短原始棒长,maxlen为给定的棒子堆中最长的棒子,sumlen为这堆棒子的长度之和,那么InitLen必定在范围[maxlen,sumlen]中

    根据棒子的灵活度(棒子越长,灵活度越低) DFS前先对所有棒子降序排序

    剪枝

    1、 由于所有原始棒子等长,那么必有sumlen%Initlen==0;

    2、 若能在[maxlen,sumlen-InitLen]找到最短的InitLen,该InitLen必也是[maxlen,sumlen]的最短;若不能在[maxlen,sumlen-InitLen]找到最短的InitLen,则必有InitLen=sumlen;

    3、 由于所有棒子已降序排序,在DFS时,若某根棒子不合适,则跳过其后面所有与它等长的棒子;

    4、 最重要的剪枝:对于某个目标InitLen,在每次构建新的长度为InitLen的原始棒时,检查新棒的第一根stick[i],若在搜索完所有stick[]后都无法组合,则说明stick[i]无法在当前组合方式下组合,不用往下搜索(往下搜索会令stick[i]被舍弃),直接返回上一层

    转载请注明:EXP 技术分享博客 » POJ1011 – Sticks

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

    表情

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

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