记录编号	403729	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[SDOI 2009]学校食堂	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	1.403 s
提交时间	2017-05-11 11:01:14	内存使用	33.69 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#define N 1005
#define inf 1061109567
#define f(i,j,k) f[i][j][k+8]
using namespace std;
int bit[10],t[N],b[N],f[N][1<<9][17],n;
//f(i,j,k)表示从左往右数第一个未满足的为i,从第i个往后7位的集合为s ,上次买第i+k个
//刷新世界观。。。。。。 
int spend(int x,int y)
{
    if(x==0) return 0;
    return t[x]^t[y];
}
int main()
{
    freopen("dining.in","r",stdin);
    freopen("dining.out","w",stdout);
    int tt;
    bit[0]=1;
    for(int i=1;i<=9;i++) bit[i]=bit[i-1]<<1;
    scanf("%d",&tt);
    while(tt--)
    {
      scanf("%d",&n);
      for(int i=1;i<=n;i++)
        scanf("%d%d",&t[i],&b[i]);
      memset(f,0x3f,sizeof(f));
      f(1,0,-1)=0;
      for(int i=1;i<=n;i++)
        for(int j=0;j<bit[8];j++)
          for(int k=-8;k<=7;k++)
            if(f(i,j,k)<inf)
            {
              if(j&1)
                f(i+1,j>>1,k-1)=min(f(i+1,j>>1,k-1),f(i,j,k));
              else{
                int lim=inf;
                for(int l=0;l<=7;l++)
                  if(!(j&bit[l])){
                    if(i+l>lim) break;
                    lim=min(lim,i+l+b[i+l]);
                    f(i,j|bit[l],l)=min(f(i,j|bit[l],l),f(i,j,k)+spend(i+k,i+l));
                  }
              }
            }
        int ans=inf;
        for(int i=-8;i<=7;i++)
          ans=min(ans,f(n+1,0,i));
        printf("%d\n",ans);
    }
    //while(1);
    return 0;
}