记录编号	175415	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[SDOI 2009]学校食堂	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	2.651 s
提交时间	2015-08-05 19:23:10	内存使用	15.91 MiB

#include<cstdio>
#include<cstring>
using namespace std;
int TEMP,EPX,C,n,bianjie,man[20],t[1111],b[1111],f[1003][256][20];
inline int in()
{
	TEMP=0;EPX=getchar();
	while(EPX<48||EPX>57)
		EPX=getchar();
	for(;EPX>47&&EPX<58;EPX=getchar())
		TEMP=(TEMP<<3)+(TEMP<<1)+EPX-48;
	return TEMP;
}
int main()
{
	freopen("dining.in","r",stdin);
	freopen("dining.out","w",stdout); 
	for(int i=0;i<20;++i)
		man[i]=(1<<i);
	C=in();
	while(C--)
	{
		n=in();
		for(int i=1;i<=n;++i)
			t[i]=in(),b[i]=in();
		memset(f,0x3f,sizeof(f));
		f[1][0][9]=0;
		for(int i=1;i<=n;++i)
			for(int j=0;j<256;++j)
				for(int k=-8;k<8;++k)
					if(f[i][j][10+k]<1000000000)
					{
						if((j&1)&&f[i+1][j>>1][9+k]>f[i][j][10+k])
							f[i+1][j>>1][9+k]=f[i][j][10+k];
						else
						{
							bianjie=0x3fffffff;
							for(int l=0;l<8;++l)
								if(!(j&man[l]))
								{
									if(l>bianjie)
										break;
									if(bianjie>l+b[i+l])
										bianjie=l+b[i+l];
									if(i+k==0&&f[i][j+man[l]][10+l]>f[i][j][10+k])//注意特判！！ 
										f[i][j+man[l]][10+l]=f[i][j][10+k];
									else if(f[i][j+man[l]][10+l]>f[i][j][10+k]+(t[i+l]^t[i+k]))
										f[i][j+man[l]][10+l]=f[i][j][10+k]+(t[i+l]^t[i+k]);
								}
						}
					}
		bianjie=0x3fffffff;
		for(int k=-8;k;++k)
			if(bianjie>f[n+1][0][10+k])
				bianjie=f[n+1][0][10+k];
		printf("%d\n",bianjie);
	}
}
//注意第三维的表示！！！以及初值！！！