Bakser's Blog

我是逗比。

bzoj1226 状压dp

| Comments

zky神犇的题解
简单讲思路
状态
f[i][j][k]代表枚举到第i个人,i..i+7的状态为j(1表示吃了,0没吃),上一个吃的人为i+k的最小代价.
转移:
若i已吃,转移到下一个人,(f[i][j][k]->f[i+1][j>>1][k-1])
若i没吃,枚举没超过忍耐限度的没吃饭的l,使l吃饭,计算代价转移(f[i][j][k]+t[i+k]^t[i+l]->f[i][j|(1<<l)][l])
边界:
f[1][0][-1]=0(没有人吃饭代价为0)
枚举顺序:
都从小向大即可.
注意事项:
1.k可能是负数,我用宏定义支持了负数下标.
2.枚举l时不能超过前面的人的界限.
3.特判第一个吃饭的人代价为0.

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define N 1010
#define f(i,j,k) (F[i][j][k+8])
#define ALL ((1<<8)-1)
#define INF 0x3f3f3f3f
#define MIN(a,b) (((a)<(b))?(a):(b))
int F[N][ALL+1][17],t[N],b[N],T,n;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d",t+i,b+i);
        memset(F,0x7f,sizeof(F));
        f(1,0,-1)=0;
        for(int i=1;i<=n;i++)
        for(int j=0;j<=ALL;j++)
        for(int k=-8;k<=7;k++)
        {
            if(f(i,j,k)>INF)continue;
            if(j&1){f(i+1,(j>>1),k-1)=MIN(f(i+1,(j>>1),k-1),f(i,j,k));continue;}
            int minn=INF;
            for(int l=0;l<8;l++)
            {
                if(j&(1<<l))continue;
                if(i+l>minn)break;
                minn=MIN(minn,i+l+b[i+l]);
                if(i+k<=0)f(i,j|(1<<l),l)=MIN(f(i,j|(1<<l),l),0);
                else f(i,j|(1<<l),l)=MIN(f(i,j|(1<<l),l),f(i,j,k)+(t[i+k]^t[i+l]));
            }
        }
        int ans=INF;
        for(int i=-8;i<0;i++)
        ans=MIN(ans,f(n+1,0,i));
        printf("%d\n",ans);
    }
    return 0;
}

Comments

comments powered by Disqus