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

    ACM-POJ EXP 186阅读 0评论

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


    大致题意

    这是POJ2533的扩展题。

    题意不难,令到原队列的最少士兵出列后,使得新队列任意一个士兵都能看到左边或者右边的无穷远处。就是使新队列呈三角形分布就对了。

    解题思路

    这里有一个陷阱,看了一些别人的解题报告说“任一士兵旁边不能存在等高的士兵”,然后又举了一个例子说注意

    3

    5 5 5

    的情况,我没看他们的程序,不知道他们是不是把这些例子特殊处理了,但完全没必要,因为“允许处于三角形顶部的两个士兵等高”,图形化就是如下图:

    其实蓝色士兵的身高和红色士兵的身高是完全没有关系的

    要求最少出列数,就是留队士兵人数最大,如图,即左边的递增序列人数和右边的递减序列人数之和最大

    因而可转化为求“最长不降子序列”和“最长不升子序列”问题

    但是不能直接套用LIS思想,因为这题不允许任一侧的序列中出现等高士兵


    基本操作方法

    对士兵的身高数组逐一进行枚举,枚举到的k值作为蓝色士兵,k+1值作为红色士兵,以这两个士兵分别作为 最长不降子序列L1 的终点和 最长不升子序列L2 的起点,即作为整个队列的分界点。

    然后分别对两边进行dp,枚举到某一个m值时,使得L1+L2的长度为最大max,此时用总士兵人数n 减去max就是 最少出列人数


    本题不能使用LIS的O(n^2)常规算法,因为一旦应用到本题,由于队列存在两段序列,要对分界点进行枚举,会导致整体时间复杂度上升到O(n^3),绝对TLE超时

    本题只能用LIS的O(n*logn)算法,具体算法步骤直接看LIS的相关介绍就有了,这里不再重复。需要注意的是要使用不同的二分法查找LIS和LDS序列,还要注意在二分查找记录数组ord[ ]时,搜索的起点和终点位置,详细可以看我的程序。

    最后就是要注意 LIS和LDS长度,还有ord的初始化(程序中我是直接释放,再重新申请的)、边界问题,全部在我的程序中都有详细体现。

    测试数据

    本文第二页附带测试数据


    转载请注明:EXP 技术分享博客 » POJ1836 – Alignment

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

    表情

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

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