题解：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\) 已经吃过饭了，那就直接向后转移即可，转移式如下：
\
这个转移式比较好理解，\(i+1\) 就是下一个同学，\(\frac{j}{2}\) 就是把 \(i\) 的吃饭状态去掉，而前一个吃完饭的人距离 \(i+1\) 的距离就是 \(k-1\)。
如果 \(j\) 的第一位为 \(0\) ，也就是 \(i\) 还没吃饭，那么就要枚举上一个吃饭的人，再进行转移，枚举的过程中要注意，因为每个人的忍耐度不一定相同，所以要判断一下是否满足前面所有人的忍耐度，转移式如下（\(l\) 就是 \(i\) 后面枚举到第几个人）：
\>>b; memset(dp,0x3f,sizeof(dp)); dp=0; for(int i=1;i1],dp); } else{ ll lst=1e18; for(int l=0;l 东西不错很实用谢谢分享 分享、互助 让互联网精神温暖你我 谢谢分享，辛苦了 很好很强大我过来先占个楼 待编辑 感谢分享，学习下。 收藏一下 不知道什么时候能用到 分享、互助 让互联网精神温暖你我 东西不错很实用谢谢分享 感谢分享，学习下。 前排留名，哈哈哈 前排留名，哈哈哈 收藏一下 不知道什么时候能用到 分享、互助 让互联网精神温暖你我 热心回复！ 热心回复！ 懂技术并乐意极积无私分享的人越来越少。珍惜 感谢分享，下载保存了，貌似很强大 懂技术并乐意极积无私分享的人越来越少。珍惜 这个有用。
页:
[1]
2