bzoj 1226: [SDOI2009]学校食堂Dining

.

题意：食堂做一道菜的时间和前一道菜有关，为(a or b)-(a and b)，有n个人在排队，可以调换顺序，但每个人最多允许紧跟在他后面的b[i]个人比他先拿到饭。求最少时间。
题解：状压DP
$f[i][j][k]$表示前$i-1$个人已经打完饭了，$i$及$i$后面的人打饭的状态为$j$，上一个打饭的人与$i$的距离为$k$（在$i$前面时$k$就是负的）。那么当i已经打到饭时，$f[i][j][k]$就可以更新$f[i+1][j>>1][k-1]$，否则就枚举现在给谁做饭，更新$f[i][1<<l|j][l]$。答案就是$min\{f[n+1][0][i]\}(i<0)$
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int c,n,t[1010],b[1010];
struct hh
{
    int a[16];
    void clear()
    {
        memset(a,63,sizeof(a));
    }
    int& operator[](int x)
    {
        return a[x+8];
    }
}f[1010][256];

int main()
{
    scanf("%d",&c);
    while(c--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        scanf("%d%d",&t[i],&b[i]);
        for(int i=1;i<=n+1;i++)
        for(int j=0;j<256;j++)
        f[i][j].clear();
        f[1][0][-1]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<256;j++)
            {
                for(int k=-8;k<=7;k++)
                {
                    if(f[i][j][k]!=0x3f3f3f3f)
                    {
//                        printf("%d %d %d %d\n",i,j,k,f[i][j][k]);
                        if(j&1)
                        {
                            f[i+1][j>>1][k-1]=min(f[i+1][j>>1][k-1],f[i][j][k]);
                        }
                        else
                        {
                            int hh=1<<30;
                            for(int l=0;l<8;l++)
                            {
                                if(!(1<<l&j))
                                {
                                    if(i+l>hh)
                                    break;
                                    hh=min(hh,i+l+b[i+l]);
                                    f[i][1<<l|j][l]=min(f[i][1<<l|j][l],f[i][j][k]+((i+k>0)?(t[i+k]^t[i+l]):0));
                                }
                            }
                        }
                    }
                }
            }
        }
        int ans=1<<30;
        for(int i=-8;i<=0;i++)
        ans=min(ans,f[n+1][0][i]);
        printf("%d\n",ans);
    }
}