题意
学生排队去食堂吃饭，每个学生都有不同的口味 $\text{T}[]$ 。食堂做第 $1$ 到菜不需要时间，之后在口味为 $x$ 的菜后做口味为 $y$ 的菜花费的时间为 $x\oplus y$ 。
为了节省总等待时间，食堂有时会不按排队顺序做，但每个同学最多忍受他后面的 $\text{B}[i]$ 个同学在他之前打饭。求等待总时间的最小值。
其中人数 $N\le 1000$ ，$\text{B}[i]\le 7$ 。
题解
用 $f[i][j][k]$ 表示第 $1$ 个人到第 $i-1$ 个人已经打完饭，第 $i$ 个人以及后面 $7$ 个人打饭的状态为 $j$ ，当前最后一个打饭的人的编号为 $i+k$ 时的最优解。
因为 $-8\le k\le 7$ ，所以给第三维每次都 $+8$ 。
如果 $j\& 1=1$ ，那么第 $1$ 个人已经打完饭了，所以可以等价的转移到 $f[i+1][j>>1][k-1]$ 。
否则就在后面 $8$ 个人中选出一个人来打饭。可以将 $\text{B}[i]$ 转化为第 $i$ 个人可以忍受的打饭的最大编号。枚举时每次对最大忍受编号取最小值，如果超过了就退出。
转移方程式为：
$$f[i][j|(1<<l)][l]=min(f[i][j|(1<<l)][l],f[i][j][k]+T[i+k]\oplus T[i+l])$$
需要注意的是第一道菜没有花费，所以当 $i+k=0$ 时就不用算 $T[i+k]\oplus T[i+l]$ 。
//f[i][j][k] 表示第 1 个人到第 i-1 个人已经打完饭，第 i 个人以及后面 7 个人是否打饭的状态为 j ，当前最后一个打饭的人的编号为 i+k
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
inline int read()
{
char ch=getchar();
int f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
const int m=1<<8;
int t,n,T[1005],B[1005],f[1005][260][20];
int main()
{
t=read();
while (t--)
{
n=read();
for (int i=1;i<=n;i++) T[i]=read(),B[i]=read();
memset(f,0x3f,sizeof(f));
f[1][0][7]=0;
for (int i=1;i<=n;i++)
{
for (int j=0;j<m;j++)
{
for (int k=-8;k<=7;k++)
{
if (f[i][j][k+8]>=inf) continue;
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 mn=inf;
for (int l=0;l<8;l++)
{
if (i+l>mn) break;
if ((j>>l)&1) continue;
mn=min(mn,B[i+l]+i+l);
f[i][j|(1<<l)][l+8]=min(f[i][j|(1<<l)][l+8],f[i][j][k+8]+(bool)(i+k)*(T[i+k]^T[i+l]));
}
}
}
}
}
int ans=inf;
for (int i=0;i<=8;i++) ans=min(ans,f[n+1][0][i]);
printf("%d\n",ans);
}
return 0;
}