题解

20 条题解

  • 1
    @ 2009-06-04 16:07:57

    Orz curimit

    奉上董华星大牛的神解:

    由题目可知,假如第i个人还没有取,则绝不可能取i+7之后的人,因为第i个人的最大容忍度不会超过7;如果第i个人之前全部取完了,则目前为止最后一个选的不可能是i-8之前的人,因为i-1不可能先于i-9及之前的人被选。故,可以设计状态f [i, S, k]表示到第i个人为止,他之前的人都取过了,他及他后面7个人的还没取过的集合是S,前一个取的人是k的最优代价。因此可以动态规划求解。

    每次枚举一个状态f [i, S, k],如果S中没有第i个人了,就将f [i, S, k]转移给f [i+1, S', k],这里S'多了第i+8个人。如果S中有第i个人,则枚举S中的一个符合要求的人j作为k之后所取的那个人,即将状态f [i, S, k]转移给f [i, S-{j}, j]。

    记录一个集合,我们可以采用二进制压位得到的整数S表示,若S and 1≠0,则说明第i个人在集合中是存在的,若S and 2≠0,说明第i+1个人在集合中是存在的,依此类推。

    而根据第一段的分析,状态的第三维的值不需要从1到N,只需要记录一个对i的相对位置就行,数值从-8到7。

    现在,就可以用状态f [i, S, k]表示到第i个人为止,他之前的人都取过了,他及他后面7个人的状态是S,前一个取的人是i+k的最优代价。对于上述两种转移,如果S表示的集合中没有第i个人了,便是将f [i, S, k]转移给f [i+1, +27, k-1];如果S表示的集合中有第i个人,则枚举其中一个符合要求的人j作为i+k之后所取的那个人,将状态转移给f [i, S-2j-i, j-i]。根据转移可以知道枚举时第一维必须从小到大枚举,第二维必须从大到小枚举。

    时间复杂度 O(2Max{B}Max2{B}N)

  • 0
    @ 2015-07-21 21:09:16

    我RP1521, 应该加个零再参加讨论~~我去也~~~~

  • 0
    @ 2015-07-21 21:07:42

    1

  • 0
    @ 2015-07-21 21:07:33

    2

  • 0
    @ 2015-07-21 21:07:29

    3

  • 0
    @ 2015-07-21 21:07:23

    我数三秒

  • 0
    @ 2015-07-21 21:06:43

    回答我,一堆紫色的大牛们!

  • 0
    @ 2015-07-21 21:05:14

    orz是什么意思啊?
    我一直没搞懂
    好尴尬的感觉~~~~~~

  • 0
    @ 2009-10-08 17:20:03

    AC得有点辛苦!把我遇到的几个问题告诉大家,希望对大家有帮助!

    1。考虑到这样的B序列 7 3 1

    可以先安排最后一个再安排第二个

    2。时间的转移应该是在一个人周围左16右16的范围内比较保险

  • 0
    @ 2009-09-15 12:58:17

    思想理解了,可是老是错,参考标程,乱改就过了。。。。。

  • 0
    @ 2009-07-19 16:08:52

    Orz voyagec2神牛。。。

    这题细节也不少啊……

  • 0
    @ 2009-06-29 11:31:48

    我的DP是用递归写的..有5个点错误216..是爆栈吗?

  • 0
    @ 2009-06-11 18:00:47

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    Orz 董华星, 我一开始想了一个压缩菜的dp, 要压14位。结果看了董华星的题解。。。

  • 0
    @ 2009-06-02 18:29:59

    这题怎么那么熟...是什么题来着阿

  • 0
    @ 2009-06-02 18:29:23

    Orz curimit voyagec2神牛

  • 0
    @ 2009-06-02 17:42:06

    状态压缩DP,压前几个人, SD day1 第三题

  • 0
    @ 2009-06-02 14:44:47

    状态压缩的动规

  • 0
    @ 2009-06-01 12:56:54

    这题..可能是要用贪心,网络流或动态规划..但是具体做法还没有想出来,我觉得应该用网络流做吧.

  • 0
    @ 2009-05-31 22:54:33

    先报到

    ^_^

    O(∩_∩)O哈哈~

  • 0
    @ 2009-05-31 20:55:39

    orz voyagec2神牛。

  • 1

信息

ID
1546
难度
6
分类
动态规划 | 状态压缩DP 点击显示
标签
递交数
171
已通过
50
通过率
29%
被复制
1
上传者