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

    ACM-POJ EXP 96阅读 0评论

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


    大致题意

    通过给定的六种操作将一个六位数变为另一个六位数,求需要的最少操作数。

    六种操作

    左移和右移:将光标位置左移一位或右移一位,在第一位时无法左移,最后一位时无法右移。

    左交换和右交换:将光标位置的数字与第一位或最后一位交换

    增大或减小:将光标位置的数字增大或减小1

    解题思路

    BFS+状态压缩


    初步想法

      很难找到有效的贪心算法

      没有明显的局部最优特性,无法动态规划

      考虑搜索


    直观的想法

      直接进行搜索,从初态开始,知道找到末态的最优解为止。

      无论空间,时间都行不通

      6个位置×1000000个不同的数=6000000个状态

      必须减少状态数


    两种操作的分离

      这六种操作对一个数有两种影响,一种是交换两个数位的位置,另一种是改变某个数位的值。

      当且仅当光标到达某一数位,对这一数位的值的改变才可能发生,而且其发生的时间并不重要。

      所以全部操作可分为两种:一种是移位和交换操作,一种是增大和减小操作。

      将操作分离成:先对原数的各数位重新排列(利用移位和交换操作),然后对光标到达过的位置进行增大或减小。


    问题转化

      1.对每一种排列和光标到达情况,求出最少需要的操作数。(此过程与输入无关)

      2.求出在每一种排列下,需要的增大和减小操作的次数。(要求所有需要改变值的数位均被访问过)


    解题第一步

      状态数

      6个位置×720种排列情况×26种光标访问情况

      进一步缩小状态数:

      因为光标是连续移动的,所以除了第6位以外,假如某一位被访问过,则它之前的数位均被访问过。第6位可用右交换操作访问,不在此列

      由此得到十种光标访问情况:

      1 被访问过

      1,2 被访问过

      1,2,3 被访问过

      1,2,3,4 被访问过

      1,2,3,4,5 被访问过

      1,6 被访问过

      1,2,6 被访问过

      1,2,3,6 被访问过

      1,2,3,4,6 被访问过

      1,2,3,4,5,6 被访问过

      现在状态数为6×720×10,可以接受了

      搜索方法

      对左移,右移,左交换,右交换四种操作进行搜索。其中不难发现左移操作是多余操作,因为可以先改变数字大小再右移或者交换

      无法预知搜索深度,最优解多在浅层获得,故采用广度优先算法


    解题第二步

      对所有满足要求的情况(即需要改变大小的数位光标都访问过),找出需要总操作最少的,输出。


    转载请注明:EXP 技术分享博客 » POJ1184 – Smart typist

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

    表情

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

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