BZOJ 1226: [SDOI2009]学校食堂Dining [DP 状压]

题意：

$n$个人排队打饭，第$i$个人口味$a_i$，能容忍最多身后第$b_i$个人先打饭。

先后两人$i,j$做饭时间为$a_i & a_j - a_i | a_j$

求最少时间

---

一开始想$f[i][s]$表示第$i$个人身后人吃饭集合$s$，第$i$个人最后吃完的状态，发现没法转移

这时候应该考虑给状态加维

$f[i][s][k]$表示前$i-1$人吃完，$i$身后包括$i$的吃饭集合为$s$，最后一个吃完的人是$k$的最短时间

如果$i$吃完了，可以直接转移到$i+1$；否则枚举下一个谁吃饭，注意满足容忍度要求

还有一点重要：$f[i]$的时候集合$s$是可以出现大于$b[i]$的人吃完饭的，因为$s$中的$i$有可能已经吃完饭了

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=,S=(<<)+,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,a[N],b[N];

inline int w(int i,int j){

    return i<= ?  : (a[i]|a[j]) - (a[i]&a[j]);

}

int f[N][S][],Z=;

int main(){

    freopen("in","r",stdin);

    int T=read();

    while(T--){

        n=read();

        for(int i=;i<=n;i++) a[i]=read(),b[i]=min(read(),n-i);

        memset(f,,sizeof(f));

        f[][][Z-]=;

        for(int i=;i<=n;i++){

            int All=<<;

            for(int s=;s<All;s++)

                for(int k=-;k<=;k++) if(f[i][s][k+Z]<INF){

                    int now=f[i][s][k+Z];

                    if(s&) {int &t=f[i+][s>>][k-+Z];t=min(t,now);continue;}

                    int lim=;

                    for(int j=;j<=lim;j++) if( ((<<j)&s)== ){

                        int &t=f[i][s|(<<j)][j+Z];

                        t=min(t,now+w(i+k,i+j));

                        lim=min(lim,j+b[i+j]);

                    }

                }

        }

        int ans=INF;

        for(int k=-;k<=-;k++) ans=min(ans,f[n+][][k+Z]);

        printf("%d\n",ans);

    }

}