[SDOI2009] 学校食堂 题解

题面：

• 有 $n$ 个人在排队打饭
  依此给出 $n$ 个人的权值，第 $i$ 人权值为 $A_i$
  输入顺序就是排队顺序（排队顺序不能变）

• 每个人还有一个容忍度，第 $i$ 个人容忍度为 $B_i$
  表示他容忍紧跟在后面的 $B_i$ 个人比他先打饭

• 给一个人打饭的花费与上一个打饭的人的权值 $A_{i1}$ 有关，设当前打饭人权值为 $A_{i2}$
  则花费为 $(A_{i1}\ or\ A_{i2})-(A_{i1}\ and\ A_{i2})$

• 让你给定一个打饭顺序，在满足所有人的容忍度情况下总花费最小

• 乍一看感觉要死，完全没有思路？怎么想都是指数级做法？

• 那就对了！因为我们缺了一个数据范围！

• 数据范围 $n\le 1000,A_i\le 1000$

• 还是没有思路？

• 最后一个数据范围 $B_i\le 7$

• ？！！！！！

• 好的这下能猜出算法了吧

• 没错就是状压dp！

• 显然需要状压的是第 $i$ 个人以后（包括 $i$ ）的打饭情况

• 我们思考还有什么会影响结果？

• 已经打过饭的人、最后一个打饭的人

• 设 $f_{i,j,k}$ 表示第 $i$ 个人以前打过饭（不包括 $i$ ）， $i$ 到 $i+B_i$ 的打饭情况为 $j$ （二进制位压缩），最后一个打饭的人是 $k$

• 列完了状态，我们来分析一下复杂度吧

• $i$ 有 $n$ 个， $j$ 有 $2^(max\ B+1)=2^8=256$ 个， $k$ 有 $n$ 个

• 转移需要枚举一个新的打饭人，转移复杂度 $8$

• 总复杂度 $n^2\times 256\times 8\approx 1000^2\times 1000=1e9$

• 时间爆炸，空间也好不到哪里去

• 但真的只能这样了吗？状态真的没有冗余吗？

• 我们发现状态中第 $i$ 人之前的都打过饭了，而这些人也有后面 $B$ 人之后不能在他之前打饭这个限定

• 所以第 $i-9$ 个人不可能是最后一个打饭的，否则第 $i-1$ 个人会在第 $i-9$ 个人之前打饭，不符合规定

• 所以 $i-8\le k\le i+7$

• 虽然有了这个范围，但还是不能直接优化，我们设 $k'=k-i+8$ ，则 $0\le k'\le 15$ ，我们有了一个正常的状态

• 设 $f_{i,j,k'}$ 表示第 $i$ 个人以前打过饭（不包括 $i$ ）， $i$ 到 $i+B_i$ 的打饭情况为 $j$ （二进制位压缩），最后一个打饭的人是 $k'+i-8$

• 到这里复杂度就降下来了，把一个 $n$ 降成了一个 $15$ 的常数

• 然而这题的实现是十分困难的，调试了不知道多久最后和题解找不同才发现错误wsl

• 要注意的有几点：

• 初值所有都是正无穷，除了几个能第一个打饭的设为0

• 在枚举下一个打饭人 $m$ 时要满足对于所有 $x$ 没有打饭且 $x < m$ 时 $m \le x + B[x] $

• 当前的 $m$ 不能已经打过饭

• 当 $f[i][j][k]$ 满足 $j\&1\neq 0$ 时，要将其转移到 $f[i+1][j>>1][k-1]$

• 最后答案取 $\min_{k=0}^8 f[n+1][0][k]$

讲完了，祝大家身体健康。