我们先约定:(左) 窗口_人人人人人 (右)

可以发现,我们只需要知道最靠左的还没打饭的人 以及它身后7个人的状态 以及上一个打饭的人是谁

因为他左面的就都打过了 右面7个人以后肯定还没打

可以设f[i][j][k]表示这是第i个人,身后7个人的状态是j,上一个打饭的是k

但其实上一个打饭的离他最远也就是8,所以可以只记i和k的差值,为了避免出负数再加个10之类的

考虑怎么转移,有两种情况

1.i身后的某个人打饭:找到j中是0的一位x,同时保证x左面的没打饭的人+这个人的容忍度<=x,也就是保证这个转移合法

2.i自己打饭:找到i右面第一个是0的位置,转移到这个位置

转移的时候更新一下k就好了

 #include<bits/stdc++.h>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> pa;
const int maxn=,maxs=,maxb=; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,v[maxn],f[maxn][maxs][maxb],b[maxn],bin[maxb]; int gettime(int i,int j,int k){
return (i+k-)?(v[i+j]|v[i+k-])-(v[i+j]&v[i+k-]):;
} int main(){
//freopen("","r",stdin);
int i,j,k,l;
bin[]=;for(i=;i<=;i++) bin[i]=bin[i-]<<;
for(int T=rd();T;T--){
N=rd();
for(i=;i<=N;i++)
v[i]=rd(),b[i]=rd();
for(i=N+;i<=N+;i++)
b[i]=;
CLR(f,);
f[][][]=;int ans=1e9+;
for(i=;i<=N;i++){
for(j=;j<bin[b[i]+];j++){
for(k=;k<=+b[i];k++){
if(f[i][j][k]>=1e9) continue;
int mi=;
for(l=;l<=b[i]&&l<=mi;l++){
if(!(j&bin[l])) f[i][j|bin[l]][l+]=min(f[i][j|bin[l]][l+],f[i][j][k]+gettime(i,l,k));
if(!(j&bin[l])) mi=min(mi,l+b[i+l]);
}
for(l=;l<=b[i];l++)
if(!(j&bin[l])) break;
f[i+l][j>>l][-l]=min(f[i+l][j>>l][-l],f[i][j][k]+gettime(i,,k));
if(i+l>N) ans=min(ans,f[i+l][j>>l][-l]);
}
}
}
printf("%d\n",ans);
}
return ;
}
05-02 07:55