BZOJ1226 SDOI2009学校食堂（状压dp）

　　由于Bi<=7，考虑状压。

　　如果考虑前i个位置的话，状态里需要压入前7个人后7个人，显然是跑不动的。

　　那么改成考虑前i个人。于是设f[i][j][k]表示前i个人都已吃完饭，i+1后面7个人的吃饭状态为j，最后一个吃饭的人是k的答案。转移时考虑下一个吃饭的是谁即可。

　　a|b-a&b=a^b。当然没什么用。

　　各种情况需要考虑的非常清楚。写的跟我一样丑的话就比较难搞了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

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

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

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 1010

int T,n,a[N],b[N],f[N][<<][],lg2[<<|],l[];

int main()

{

#ifndef ONLINE_JUDGE

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

    freopen("bzoj1226.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    T=read();

    for (int i=;i<=;i++) lg2[<<i]=i;

    while (T--)

    {

        int n=read();

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

        memset(f,,sizeof(f));

        f[][][]=;

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

            for (int j=;j<(<<min(,n-i-));j++)

            {

                l[]=min(i++b[i+],n);

                for (int k=;k<;k++)

                if (!(j&(<<k-))) l[k]=min(l[k-],i+k++b[i+k+]);

                else l[k]=l[k-];

                for (int k=;k<;k++)

                if (k<=&&i+k->=||k>=&&(j&(<<k-)))

                {

                    f[i++lg2[j+&-(j+)]][j>>lg2[j+&-(j+)]+][-lg2[j+&-(j+)]]=

                    min(f[i++lg2[j+&-(j+)]][j>>lg2[j+&-(j+)]+][-lg2[j+&-(j+)]],f[i][j][k]+(i+k-?(a[i+k-]^a[i+]):));

                    for (int x=;x<=;x++)

                    if (!(j&(<<x-))&&i+x+<=l[x-])

                    f[i][j|(<<x-)][+x]=min(f[i][j|(<<x-)][+x],f[i][j][k]+(i+k-?(a[i+k-]^a[i+x+]):));

                }

            }

        for (int i=;i<;i++) f[n][][]=min(f[n][][],f[n][][i]);

        cout<<f[n][][]<<endl;

    }

    return ;

}

巴特西

BZOJ1226 SDOI2009学校食堂（状压dp）

最新文章

热门文章