[BZOJ1226][SDOI2009][状态压缩DP]学校食堂Dining

时间：2022-09-08 04:28:22

<题目>

小F 的学校在城市的一个偏僻角落，所有学生都只好在学校吃饭。学校有一个食堂，虽然简陋，但食堂大厨总能做出让同学们满意的菜肴。当然，不同的人口味也不一定相同，但每个人的口味都可以用一个非负整数表示。由于人手不够，食堂每次只能为一个人做菜。做每道菜所需的时间是和前一道菜有关的，若前一道菜的对应的口味是a，这一道为b，则做这道菜所需的时间为（a or b）-（a and b），而做第一道菜是不需要计算时间的。其中，or 和and 表示整数逐位或运算及逐位与运算，C语言中对应的运算符为“|”和“&”。学生数目相对于这个学校还是比较多的，吃饭做菜往往就会花去不少时间。因此，学校食堂偶尔会不按照大家的排队顺序做菜，以缩短总的进餐时间。虽然同学们能够理解学校食堂的这种做法，不过每个同学还是有一定容忍度的。也就是说，队伍中的第i 个同学，最多允许紧跟他身后的Bi 个人先拿到饭菜。一旦在此之后的任意同学比当前同学先拿到饭，当前同学将会十分愤怒。因此，食堂做菜还得照顾到同学们的情绪。现在，小F 想知道在满足所有人的容忍度这一前提下，自己的学校食堂做完这些菜最少需要多少时间。

<算法>

状态压缩DP

<分析>

影响决策的因素主要有两个，一是上一个吃饭的同学，二是前面有哪些同学已经吃了饭。所以用f[i][st][last]表示前(i-1)个同学已经吃了饭，第i到第(i+7)个同学是否吃饭的状态为st，上一个吃饭的同学与i同学的相对距离为last

转移分两种情况

  1.  当i已经吃了的时候，就可以转移到f[i+1][st>>1][last-1]

  2. 枚举下一个吃饭的人k,进行转移，注意判断是否合法（即有没有前面的人不愿意让他先吃饭）

<注意>

  1. 位运算的优先级问题，搞不清楚一定要多加括号

  2. 由于相对位置那一维状态会出现负数，不要忘了加上一个常数

<鸣谢>

感谢ZKY神犇的题解，以下为链接：

http://blog.csdn.net/iamzky/article/details/23284013

<代码>

/**************************************************************
    Problem: 1226
    User: gaotianyu1350
    Language: C++
    Result: Accepted
    Time:2828 ms
    Memory:23280 kb
****************************************************************/

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;

#define MAXN 1100
#define M    10
#define INF  1000000000

int taste[MAXN],bear[MAXN];
int f[MAXN][1<<8][M*2];
int n,testcase;

int main()
{
    //freopen("input.txt","r",stdin);
    scanf("%d",&testcase);
    while (testcase--)
    {
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
            scanf("%d%d",&taste[i],&bear[i]);
        memset(f,0x7f,sizeof(f));
        f[1][0][M-1]=0;
        bear[0]=INF;
        for (int i=1;i<=n;i++)
        for (int st=0;st<(1<<8);st++)
        for (int last=-8;last<8;last++)
        {
            int k=last+M;
            if (f[i][st][k]>INF) continue;
            //i Have Already Eat
            if (st&1)
                f[i+1][st>>1][k-1]=min(f[i+1][st>>1][k-1],f[i][st][k]);
            //Chose Next Eater
            int youcango=INF;
            for (int next=0;next<=7;next++)
            {
                if (((st>>next)&1)==0)
                {
                    if (i+next<=youcango)
                        if (i+last>0)
                            f[i][st|(1<<next)][next+M]=min(f[i][st|(1<<next)][next+M],f[i][st][k]+(taste[i+last]|taste[i+next])-(taste[i+last]&taste[i+next]));
                        else
                            f[i][st|(1<<next)][next+M]=min(f[i][st|(1<<next)][next+M],0);   
                    youcango=min(youcango,i+next+bear[i+next]);
                    if (i+next>=youcango) break;
                }
            }
        }
        int ans=INF;
        for (int i=-8;i<0;i++)
            ans=min(ans,f[n+1][0][i+M]);
        printf("%d\n",ans);
    }
}




标签：

相关文章