Description:

食堂中每个人的菜有一个值 $t[i]$ ，为他做菜所花的时间为 $t[i] \wedge t[j]$ ， $j$ 是做的上一道菜的值，第 $i$ 个人会允许 $b[i]$ 个他之后的人比他先打饭，求使所有人打完饭的最短时间

$ 1 \le N \le 1000 $ $ 0 \le B_i \le7 $

Solution:

$B_i$ 很小，只有 $7$ ，用状压来表示吃饭的情况

$ f[i][j][k] $ 表示到了第 $i$ 个人，前 $i-1$ 个人已经吃完饭， $i$ 及 $i$ 之后的人的吃饭情况为 $j$ ， $i$ 上一个吃饭的人与他的相对位置是 $k$

初值 $f[1][0][-1] = 0$ ，其余的都赋成 $INF$

用顺推法：

1、若 $j\&1==1$ ，前 $i$ 个人已经吃完饭，可以向后转移， $j$ 向右移了一位（ $i+k=(i+1)+(k-1)$ ） $$f[i][j][k] \to f[i+1][j>>1][k-1]$ $

2、若 $j\&1$ $ != 1$ ，第 $i$ 个人还没吃饭，那就在 $j$ 中选一个没有吃饭的（包括他自己）让他吃饭

$f[i][j][k]+calc(i+k,i + p)\to f[i][j|(1<<p)][p] (calc(i,j) = (i?t[i]\wedge t[j] : 0))$

注意第二种转移的合法性，如果要让 $i+p$ 吃饭，则 $i\dots i+p-1$ 都要同意才行，从 $0$ 开始枚举，维护一个当前合法的右边界 $rig$ ，如果 $i+p>rig$ 则 $break$ ，注意只有 $j$ 中没有吃饭的才能更新 $f$ 和 $rig$ 。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define INF 0x3f3f3f3f

int testcases;

int n;

#define MAXN 1010

#define MAXB 8

int F[MAXN][1 << MAXB][MAXB * 2];

int t[MAXN],b[MAXN];

int calc(int x,int y)

{

	if(x <= 0)return 0;

	else return (t[x] ^ t[y]);

}

#define f(a,b,c) (F[a][b][c + 8])

void work()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d",&t[i],&b[i]);

	}

	memset(F,INF,sizeof(F));

	f(1,0,-1) = 0;

	for(int i = 1;i <= n + 1;++i)

	{

		for(int j = 0;j < (1 << 8);++j)

		{

			for(int k = -8;k <= 7;++k)

			{

				if(f(i,j,k) >= INF)continue;

				if(j & 1)

				{

					f(i + 1,j >> 1,k - 1) = min(f(i + 1,j >> 1,k - 1),f(i,j,k));

				}

				else

				{

					int rig = INF; 

					for(int l = 0;l <= 7;++l)

					{

						if(!(j & (1 << l)))	

						{

							if(i + l > rig)break;

							rig = min(rig,i + l + b[i + l]);

							f(i,j | (1 << l),l) = min(f(i,j | (1 << l),l),f(i,j,k) + calc(i + k,i + l));

						}

					}

				}

			}

		}

	}

	int ans = INF;

	for(int k = -8;k <= -1;++k)

	{

		ans = min(ans,f(n + 1,0,k));

	}

	cout << ans << endl;

	return;

}

int main()

{

	scanf("%d",&testcases);

	for(int i = 1;i <= testcases;++i)work();

	return 0;

}