洛谷2157 [SDOI2009]学校食堂

access_time    bookmark 题解    comment 0 条评论    省选/NOI-

题意

学生排队去食堂吃饭,每个学生都有不同的口味 $\text{T}[]$ 。食堂做第 $1$ 到菜不需要时间,之后在口味为 $x$ 的菜后做口味为 $y$ 的菜花费的时间为 $x\oplus y$ 。

为了节省总等待时间,食堂有时会不按排队顺序做,但每个同学最多忍受他后面的 $\text{B}[i]$ 个同学在他之前打饭。求等待总时间的最小值。

其中人数 $N\le 1000$ ,$\text{B}[i]\le 7$ 。

题解

用 $f[i][j][k]$ 表示第 $1$ 个人到第 $i-1$ 个人已经打完饭,第 $i$ 个人以及后面 $7$ 个人打饭的状态为 $j$ ,当前最后一个打饭的人的编号为 $i+k$ 时的最优解。

因为 $-8\le k\le 7$ ,所以给第三维每次都 $+8$ 。

如果 $j\& 1=1$ ,那么第 $1$ 个人已经打完饭了,所以可以等价的转移到 $f[i+1][j>>1][k-1]$ 。

否则就在后面 $8$ 个人中选出一个人来打饭。可以将 $\text{B}[i]$ 转化为第 $i$ 个人可以忍受的打饭的最大编号。枚举时每次对最大忍受编号取最小值,如果超过了就退出。

转移方程式为:

$$f[i][j|(1<<l)][l]=min(f[i][j|(1<<l)][l],f[i][j][k]+T[i+k]\oplus T[i+l])$$

需要注意的是第一道菜没有花费,所以当 $i+k=0$ 时就不用算 $T[i+k]\oplus T[i+l]$ 。

//f[i][j][k] 表示第 1 个人到第 i-1 个人已经打完饭,第 i 个人以及后面 7 个人是否打饭的状态为 j ,当前最后一个打饭的人的编号为 i+k

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

const int m=1<<8;
int t,n,T[1005],B[1005],f[1005][260][20];

int main()
{
    t=read();
    while (t--)
    {
        n=read();
        for (int i=1;i<=n;i++) T[i]=read(),B[i]=read();
        memset(f,0x3f,sizeof(f));
        f[1][0][7]=0;
        for (int i=1;i<=n;i++)
        {
            for (int j=0;j<m;j++)
            {
                for (int k=-8;k<=7;k++)
                {
                    if (f[i][j][k+8]>=inf) continue;
                    if (j&1) f[i+1][j>>1][k+7]=min(f[i+1][j>>1][k+7],f[i][j][k+8]);
                    else
                    {
                        int mn=inf;
                        for (int l=0;l<8;l++)
                        {
                            if (i+l>mn) break;
                            if ((j>>l)&1) continue;
                            mn=min(mn,B[i+l]+i+l);
                            f[i][j|(1<<l)][l+8]=min(f[i][j|(1<<l)][l+8],f[i][j][k+8]+(bool)(i+k)*(T[i+k]^T[i+l]));
                        }
                    }
                }
            }
        }
        int ans=inf;
        for (int i=0;i<=8;i++) ans=min(ans,f[n+1][0][i]);
        printf("%d\n",ans);
    }
    return 0;
}

新评论

account_circle
称呼不能为空
email
邮箱格式不合法
link
网站格式不合法
textsms
内容不能为空

第一次提交或含有敏感词汇的评论将在审核后显示。