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

    ACM-POJ EXP 158阅读 0评论

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


    大致题意

    给定一堆不定长度的小棒子,问他们能否构成一个正方形。

    解题思路

    POJ1011 的热身题,DFS+剪枝

    本题大致做法就是对所有小棒子长度求和sum,sum就是正方形的周长,sum/4就是边长side。

    问题就转变为:这堆小棒子能否刚好组合成为4根长度均为side的大棒子

    不难了解,小棒子的长度越长,其灵活性越差。例如长度为5的一根棒子的组合方式要比5根长度为1的棒子的组合方式少,这就是灵活性的体现。

    由此,我们首先要对这堆小棒子降序排序,从最长的棒子开始进行DFS


    剪枝,有3处可剪:

    1、 要组合为正方形,必须满足sum%4==0;

    2、 所有小棒子中最长的一根,必须满足Max_length <= side,这是因为小棒子不能折断;

    3、 当满足条件1、2时,只需要能组合3条边,就能确定这堆棒子可以组合为正方形。

    转载请注明:EXP 技术分享博客 » POJ2362 – Square

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

    表情

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

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