bzoj1226: [SDOI2009]学校食堂Dining

这题状压DP。

f[i][j][k]表示前i-1吃了，后面几个吃的人的方案为j，最后吃的是第i+k个人。

然后如果j&1>0可以直接转移到f[i+1][(j>>1)][k]

其他还可以转移到f[i][j+(1<<l)][l]

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define f(a,b,c) zheshibushikeyixiajibadingyiya[a][b][c+8]
using namespace std;
const int inf=(1<<30);

int a[1100],b[1100];
int zheshibushikeyixiajibadingyiya[1100][310][20];//前i-1吃了，剩下吃的人的方案为j，最后吃的是第i+k个人 
int cal(int x,int y)
{
    if(x==0)return 0;
    return a[x]^a[y];
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&a[i],&b[i]), b[i]=min(b[i],n-i);
        
        for(int i=1;i<=n+1;i++)
            for(int j=0;j<=255;j++)
                for(int k=-8;k<=7;k++)
                    f(i,j,k)=inf;
        f(1,0,-1)=0;
        
        for(int i=1;i<=n;i++)
            for(int j=0;j<=255;j++)
                for(int k=-8;k<=7;k++)
                    if(f(i,j,k)<inf)
                    {
                        if((j&1)>0)f(i+1,(j>>1),k-1)=min(f(i+1,(j>>1),k-1),f(i,j,k));
                        else
                        {
                            int r=inf;
                            for(int l=0;l<=7;l++)
                            {
                                int bl=(1<<l);
                                if((j&bl)==0)
                                {
                                    if(l+i>r)break;
                                    r=min(r,l+i+b[i+l]);
                                    f(i,j+bl,l)=min(f(i,j+bl,l),f(i,j,k)+cal(i+k,i+l));
                                }
                            }
                        }
                    }
        
        int ans=inf;
        for(int k=-8;k<=-1;k++)
            ans=min(ans,f(n+1,0,k));
        printf("%d\n",ans);
    }
    return 0;
}