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)

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

1

2

3

我数三秒

回答我，一堆紫色的大牛们！

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

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

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

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

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

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

Orz voyagec2神牛。。。

这题细节也不少啊……

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

编译通过...

├ 测试数据 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位。结果看了董华星的题解。。。

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

Orz curimit voyagec2神牛

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

状态压缩的动规

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

先报到

^_^

O(∩_∩)O哈哈~

orz voyagec2神牛。