状态压缩 转移判断

dp不一定是转移到i就要对i进行处理  可以表示一个范围 且同层i也可以互相转移

/**************************************************************    Problem: 1226    User: lxy8584099    Language: C++    Result: Accepted    Time:2508 ms    Memory:21828 kb****************************************************************/ /*满足忍耐度就枚举忍耐度的范围 选取可行的忍耐度f i,j,k 表示前i-1的人已经拿到饭  (本次给i做菜    j表示i～i+bi的状态 k表示上一次拿到饭菜的人相对i的位置j的取值是 0～2^8-1 k的取值是-7~7  为了方便 整体+8NOTE:第一道菜是不需要计算时间的*/#include
     
      #include
      
       using namespace std;const int N=1050;int f[N][1<<8][20],n,t[N],b[N],res,inf,T;int clac(int i,int k,int l){    if(i+k==0) return 0;  // 判断一下k是不是从位置0转移过来的    return (t[i+k]^t[i+l]);}void getmin(int&a,int b) {
   if(a>b) a=b;}int main(){    scanf("%d",&T); while(T--)    {        scanf("%d",&n); res=0x3fffffff;        for(int i=1;i<=n;i++) scanf("%d%d",&t[i],&b[i]);        memset(f,0x3f,sizeof(f)); inf=f[0][0][0]; f[1][0][7]=0; //f[1][0][7] 7表示7-8=-1 就是1后面一 也就是0        for(int i=1;i<=n;i++)        for(int j=0;j<(1<<8);j++)        for(int k=-8;k<=7;k++) if(f[i][j][k+8]!=inf) //         {            if(j&1&&k!=-8) getmin(f[i+1][j>>1][k+8-1],f[i][j][k+8]);// 第i位已经就绪 就可以任意选择k 直接往后面转移就行了// 否则没办法转移到i+1 （因为fi的含义是1～i-1全部就绪）// 就只有枚举本次由谁来打饭 不过又要满足i之后人的忍耐值  所以维护一个maxr 美剧大于maxr就break            else            {                int maxr=n;                for(int l=0;l<=7;l++) if(!((1<
       
        maxr) break; // 适当break                    getmin(maxr,i+l+b[i+l]);//更新maxr                    getmin(f[i][j|(1<