[题解]luogu_P2157学校食堂（状压dp

n个人排队打饭，每个人可以容忍在他后面的b[i]个人在他前面打饭，每次打饭的时间消耗为两个人权值异或（或-与），问最短时间

小数据范围一定要想状压，b[i]<=7提示我们状压当前这个人周围的7个(左右)的人，要算每次消耗的时间还要再记上一个打饭的人，注意这个人不可能在某人后面或前面7位以上，所以直接记这个人和当前人的相对位置即可

所以$f[i][j][k]$表示前$i-1$个人打完饭，$i~i+7$个人的状态为j，上一个打饭的人为$i+k(-8<=k<=7)$的最小花费，k可负要加偏移量（文中均未加偏移量

然后想转移，无非是枚举下一个人是谁，但是如果i打过饭了那么i+1也可以更新了，不要再在i处更新了，即如果$(j&1),f[i+1][j>>1][k-1]=min(f[i+1][j>>1][k-1],f[i][j][k])$，可以看出这两个状态等价

如果$!(j&1)$，就枚举下一个人$i+h(0<=h<=7)$，但是注意每个人都有限制，不妨从小到大枚举h，这样限制h的人会越来越多，一旦不合法直接break，很方便

答案为$max(f[n+1][0][k])(-8<=k<=0)$，

#include<bits/stdc++.h>
using namespace std;
const int maxn=1009;
const int inf=0x3f3f3f3f;
int n,T,t[maxn],b[maxn];
int f[maxn][1<<8][20];//1~i-1已打完 i~i+7打饭状态为s 上一个打饭的为i+k 
int main(){scanf("%d",&T);
    while(T--){
        memset(f,0x3f,sizeof(f));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d%d",&t[i],&b[i]);
        f[1][0][7]=0;//前0个人打完饭上一个打饭的是0消耗为0 
        for(int i=1;i<=n;i++){
            for(int j=0;j<(1<<8);j++)
            for(int k=-8;k<=7;k++)
            if(f[i][j][k+8]!=inf){
                if(j&1)f[i+1][j>>1][k+7]=min(f[i+1][j>>1][k+7],f[i][j][k+8]);
                else{
                    int lmt=inf;
                    for(int h=0;h<=7;h++)
                    if(!((j>>h)&1)){
                        if(i+h>lmt)break;
                        lmt=min(lmt,i+h+b[i+h]);//对于往后枚举h lmt会被更多人限制 所以可以这么推 
                        f[i][j|(1<<h)][h+8]=min(f[i][j|(1<<h)][h+8],f[i][j][k+8]+(i+k?(t[i+k]^t[i+h]):0));
                    }
                }
            }
        }
        int ans=inf;
        for(int i=0;i<=8;i++)
        ans=min(ans,f[n+1][0][i]);
        printf("%d
",ans);
    }
}