记录编号	407574	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[SDOI 2009]学校食堂	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	2.827 s
提交时间	2017-05-22 12:06:19	内存使用	39.55 MiB

#include <cstdio>
#include <cstring>
#define f(i,j,k) f[i][j][k+8]
namespace qread{
	const int MAXN = 1005;
	int f[MAXN][1<<9][20],c,n,t[MAXN],b[MAXN],bit[15];
	inline void read(int &x){
		x=0;int f=1;
		char ch;
		while(ch<'0'||ch>'9'){
			if(ch=='-')
				f=-f;
			ch=getchar();
		}
		while(ch>='0'&&ch<='9'){
			x=x*10+ch-'0';
			ch=getchar();
		}
		x=x*f;
	}
	inline void read(int &x,int &y){read(x);read(y);}
	inline int min (int x,int y){return x<y?x:y;}
	inline int var (int x,int y){if(x==0)return 0;return t[x]^t[y];}
}
using namespace qread;


int main(){
#define file
#ifdef file
	freopen("dining.in","r",stdin);
	freopen("dining.out","w",stdout);
#endif
	read(c);
	bit[0]=1;
	for(int i=1;i<=10;i++)
		bit[i]=bit[i-1]<<1;
	while(c--){
		memset(f,0x3f,sizeof(f));
		read(n);
		for(int i=1;i<=n;i++)
			read(t[i],b[i]);
		f[1][0][7]=0;
		for(int i=1;i<=n;i++){
			for(int j=0;j<bit[8];j++)
				for(int k=-8;k<=7;k++){
					if(j&1)f(i+1,j>>1,k-1)=min(f(i,j,k),f(i+1,j>>1,k-1));
					else{
						int A=0x7fffffff;
						for(int p=0;p<=7;p++){
							if(j&bit[p])continue;
							if(i+p>A)break;
							A=min(A,i+p+b[i+p]);
							f(i,j|bit[p],p)=min(f(i,j|bit[p],p),f(i,j,k)+var(i+k,i+p));
						}
					}
				}
		}
		int ans=0x7fffffff;
		for(int i=-8;i<=7;i++)
			ans=min(ans,f(n+1,0,i));
		printf("%d\n",ans);
	}
	return 0;
}