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

    ACM-POJ EXP 189阅读 0评论

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


    大致题意

    有一块边长为BoxSize的正方形的大蛋糕,现在给出n块不同尺寸的正方形的小蛋糕的边长,问是否能把大蛋糕按恰好切割为这n块小蛋糕,要求每块小蛋糕必须为整块。

    解题思路

    有技巧的DFS

    可以把大蛋糕想象为一个蛋糕盒子,然后往里面装小蛋糕。

    装蛋糕时遵循以下原则:

    自下而上,自左至右;

    即先装好盒子底部,再继续往上层装,且装每一层时都靠左边放蛋糕;

    大蛋糕优先装,因为小蛋糕灵活度比较高。

    只要把问题变换为上述问题,我想对深搜比较熟悉的同学也会马上得到思路了,这个只是很简单的DFS思路。


    但是本题的难点不在于怎样去DFS,而是每放入一个蛋糕后,怎样去标记盒子已经放有蛋糕的位置

    我初始的做这题时,因为看到数据规模不大(Max_n=16,Max_size=10,那么大蛋糕最大也就40*40),于是我把尺寸为BoxSize的盒子划分为BoxSize*BoxSize个1*1的格子,每放入一个大小为size的蛋糕,就用一个二重循环去标记size*size的格子。

    最后是毫无悬念地TLE了。

    看了别人的方法,发现或分格子的思路是正确的,但应该“按列标记”。不但把盒子看做多个1*1个格子,也把小蛋糕看做多个1*1的单位,建立一个一维数组col[ BoxSize ],每放入一个蛋糕,则去记录每列的格子被填充的数目。

    例如在第2~4列放入了一个size=3的小蛋糕,那么col[2]+=3, col[3]+=3, col[4]+=3。有同学会问,为什么行不用计数?要是放入蛋糕后,该蛋糕底部出现部分悬空怎么处理?这个情况是不会出现的,因为当前DFS遵循先把底部放满原则,要是出现悬空,则会回溯。

    更具体的处理方法请看程序注释。

    Source修正

    Tehran 2002, First Iran Nationwide Internet Programming Contest(已失效)-问题E

    测试数据

    本文第二页附带测试数据


    转载请注明:EXP 技术分享博客 » POJ1020 – Anniversary Cake

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

    表情

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

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