自从开始复习DP，我就天天抄题解
第一眼看到题目：我是谁？我在哪？我要干什么？
注意到$B$的范围十分友好，明显要状压。我要状压啥？
于是愉悦地抄起了题解
$f(i,st,k)$表示前$i-1$个人已经吃完，第$i$个人到第$i+7$个人的状态为$st$（$0$为没吃，$1$为吃了）最短时间。因为做一道菜的时间和上一道有关系，所以用$k$表示上一个吃的人为第$i+k$个人$(k\in [-8,7])$。
Q：为啥k的意义这么奇怪？不能直接用k表示上一个吃的人为k？
A：可以发现上一个吃的人范围一定在$[i-8,i+7]$内，超出这个范围这个状态就是不合法的，就能直接省掉空间与时间。
初始状态：$f(1,0,-1)=0$（没有人吃饭，第$1$个人到第$8$个人都没吃饭，上一道菜为第$0$道，即还没有做菜）
考虑转移：
- 如果$st$第一位为$1$（第$i$个人吃了），那就直接向$f(i+1,st>>1,k-1)$转移。这两个状态其实是一样的，不用枚举下一个谁吃饭。
- 如果$st$第一位为$0$，枚举下一个谁吃了，转移到$f(i,st|(1<<j),j)$，还要注意满足每个人的容忍度，记录当前最大能吃饭的人的范围，一但超出就停止。
答案即为$\min \{f(n+1,0, -8)\sim f(n+1,0,0)\}$
Q：为什么不考虑不合法的状态呢？
比如说$st$中第3个人没吃，第6个人吃了，而第3个人容忍度为2，这样转移不就错了吗？
A：转移时都是向合法的状态转移，不合法的都被过滤掉了。所以当遇到不合法状态时，它从未被转移过，值也就为$inf$。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 1005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
int t[maxn],b[maxn],F[maxn][1<<9][20],*f[maxn][1<<9];
inline int calc(int i,int j){
if(!i)return 0;
return t[i]^t[j];
}
//t[i]|t[j]-t[i]&t[j]就相当于t[i]^t[j]
int main(){
int c=read();
for(register int i=0;i<maxn;++i)
for(register int j=0;j<(1<<9);++j)
f[i][j]=&F[i][j][10];
//小技巧：用指针处理可以使数组访问负数下表
while(c--){
int n=read();
for(register int i=1;i<=n;++i)
t[i]=read(),b[i]=read();
memset(F,0x3f,sizeof F);
f[1][0][-1]=0;
for(register int i=1;i<=n;++i){
for(register int st=0;st<(1<<8);++st)
for(register int k=-8;k<=7;++k){
if(f[i][st][k]==inf)continue;
if(1&st)
f[i+1][st>>1][k-1]=min(f[i+1][st>>1][k-1],f[i][st][k]);
else {
for(register int j=0,li=7;j<=li;++j)//li是最大容忍范围
if(!((1<<j)&st)){
f[i][st|(1<<j)][j]=min(f[i][st|(1<<j)][j],f[i][st][k]+calc(i+k,i+j));
li=min(li,j+b[i+j]);
}
}
}
}
int ans=inf;
for(register int i=-8;i<=0;++i)
ans=min(ans,f[n+1][0][i]);
printf("%d\n",ans);
}
}
