luogu 2157 [SDOI2009]学校食堂 状压dp

#include <bits/stdc++.h> 
#define N 1005   
#define inf 0x3f3f3f3f   
#define setIO(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
using namespace std;
int n;
int t[N],b[N],f[N][1<<10][20];
inline int Num(int x) { return x+8; }
inline void getmin(int &a,int b)  { if(b<a) a=b; }
void solve() 
{ 
	// setIO("candy");     
	int i,j,k,h;        
	scanf("%d",&n); 
	for(i=1;i<=n;++i)     scanf("%d%d",&t[i],&b[i]);        
	memset(f,inf,sizeof(f)); 
	f[1][0][Num(-1)]=0;                                  
    for(i=1;i<=n;++i)    
	{
	    for(j=0;j<(1<<8);++j)       
		{           
			for(k=-8;k<=7;++k) 
			    if(f[i][j][Num(k)]!=inf) 
				{
					if (j&1) 
					    getmin(f[i+1][j>>1][Num(k-1)],f[i][j][Num(k)]);
					else 
					{
						int tmp=inf;
						for (h=0;h<=7;++h) 
							if (!((j>>h)&1)) 
							{
								if(i+h>tmp) break;
								getmin(tmp,i+h+b[i+h]);
								getmin(f[i][j|(1<<h)][Num(h)],f[i][j][Num(k)]+(i+k?(t[i+k]^t[i+h]):0));
							}
					}
                } 
		}
	} 
	int res=inf;   
	for(i=0;i<=8;++i)   res=min(res, f[n+1][0][i]);       
	printf("%d\n",res);     
}   
int main() 
{
	int T; 
	scanf("%d",&T); 
	while(T--) solve();     
}