题解：P2157 [SDOI2009] 学校食堂

题目传送门

题目大意

有 \(n\) 个学生，每个学生有一个时间 \(t_i\)，所花费的真实时间为 \(t_i\) 异或上前一个吃饭的同学的 \(t_i\)。每个学生有一个忍耐度，最多可以让后面 \(b_i\) 个同学比自己先吃饭。问在不违反忍耐度的条件下，让所有同学吃饭的最小时间。
解题思路

首先，我们发现 \(b_i\) 很小，考虑状压。状态设置比较离奇，\(dp_{i,j,k}\) 表示到第 \(i\) 个同学，后面7个同学，包括自己的吃饭的状态，\(0\) 是还没吃饭，\(1\) 是吃饭了，\(k\) 表示上一个吃饭的人距离 \(i\) 的距离，所以 \(-8\le k\le 7\)。
现在我们考虑转移，首先如果枚举到的 \(j\) 中，\(j\) 的第一位为 \(1\) ，也就是 \(i\) 已经吃过饭了，那就直接向后转移即可，转移式如下：

\[dp_{i+1,\frac{j}{2},k-1}=dp_{i,j,k}\]
这个转移式比较好理解，\(i+1\) 就是下一个同学，\(\frac{j}{2}\) 就是把 \(i\) 的吃饭状态去掉，而前一个吃完饭的人距离 \(i+1\) 的距离就是 \(k-1\)。
如果 \(j\) 的第一位为 \(0\) ，也就是 \(i\) 还没吃饭，那么就要枚举上一个吃饭的人，再进行转移，枚举的过程中要注意，因为每个人的忍耐度不一定相同，所以要判断一下是否满足前面所有人的忍耐度，转移式如下（\(l\) 就是 \(i\) 后面枚举到第几个人）：

\[dp_{i+1,j|(1n;        for(int i=1;i>t>>b;        memset(dp,0x3f,sizeof(dp));        dp[1][0][7]=0;        for(int i=1;i1][k-1],dp[j][k]);                    }                    else{                        ll lst=1e18;                        for(int l=0;l