# [sdoi2009]学校食堂dining（洛谷2157）

Posted by yjjr's blog on February 6, 2018

2

5

5 2

4 1

12 0

3 3

2 2

2

5 0

4 0

16

1

【数据规模和约定】

J可以用二进制来表示，0表示没吃，1表示吃过了

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
#define f(a,b,c) g[a][b][c+8]
using namespace std;

const int maxn=1006,inf=0x3f3f3f;
int g[maxn][1<<8][16];
int a[maxn],b[maxn],bin[20],T,n;

inline int calc(int x,int y){
if(!x)return 0;
else return (a[x]|a[y])-(a[x]&a[y]);
}
int main()
{
bin[0]=1;
rep(i,1,10)bin[i]=bin[i-1]<<1;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
rep(i,1,n)scanf("%d%d",&a[i],&b[i]);
rep(i,1,n+1)rep(j,0,bin[8]-1)rep(k,-8,7)f(i,j,k)=inf;
f(1,0,-1)=0;
rep(i,1,n)
rep(j,0,bin[8]-1)
rep(k,-8,7)
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 r=inf;
rep(l,0,7)
if((j&bin[l])==0){
if(i+l>r)break;
r=min(r,i+l+b[i+l]);
f(i,j^bin[l],l)=min(f(i,j^bin[l],l),f(i,j,k)+calc(i+k,i+l));
}
}
}
int ans=inf;
rep(k,-8,-1)ans=min(ans,f(n+1,0,k));
printf("%d\n",ans);
}
return 0;
}