P2154 SDOI2009 学校食堂题解（状压

· · 题解

题解

其他大佬写的都很好了，我就来写下解这种题的过程吧。。。

题目分析

求出一个学生吃饭的顺序，使得时间最短

怎样才能短？？？？ 用（a or b）-（a and b）计算时间

首先看题目：发现这个人不仅和前面人又关，还和后面人有关，啧啧啧

再看数据范围

存在30%的数据，满足0 ≤ Bi ≤ 1。(可以骗分，美滋滋

对于100%的数据，满足1 ≤ N ≤ 1,000，0 ≤ Ti ≤ 1,000，0 ≤ Bi ≤ 7，1 ≤ C ≤ 5。

只能让后面7个人插队，岂不是可以状态压缩

拿到题目先打暴力

dp方程 ： f[i] [j] [k]

表示：前i个学生都吃过了（都！！！）；后面学生吃过与否的状况用j表示（00010...）；最后吃的学生和i的距离为k

计算式

我们会发现这个看似复杂的式子，其实就是^运算（真的皮

开始操盘

首先dp预处理。

    memset(f,INF,sizeof(f));f[1][0][7]=0;

dp分情况转移（分类讨论

    for(int i=1;i<=n;i++) 
    for(int j=0;j<(1<<8);j++)
    for(int k=-8;k<=7;k++) 
    if(f[i][j][k+8]!=INF)
分类开始

如果 i 吃过了，则可以转移

    if(j&1) f[i+1][j>>1][k+7]=min(f[i+1][j>>1][k+7],f[i][j][k+8]);

因为转移方程是前i个都吃过了，所以i没吃是没法转移的。

不过我们可以通过后面同学插队来解决

    memset(f,INF,sizeof(f));f[1][0][7]=0;
    for(int i=1;i<=n;i++) 
    for(int j=0;j<(1<<8);j++)
    for(int k=-8;k<=7;k++) 
    if(f[i][j][k+8]!=INF) {
            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 limit=INF;
                for(int h=0;h<=7;h++) if(!((j)&(1<<h))) {//i没吃没法转移方程，但可以枚举后面学生来满足方程:(前i个人吃过),（由数据可知最多7人）
                    if(i+h > limit) break;
                    limit=min(limit,i+h+B[i+h]);//当枚举i后面学生到前面插队时，如果要让他插队，应该注意是否满足i后每一位学生的忍容度限制 
                    f[i][j|(1<<h)][h+8]=min( f[i][j|(1<<h)][h+8] , f[i][j][k+8] + (i+k?(T[i+k]^T[i+h]):0) );
                    //当满足上述条件时，就可以让第i+h位同学插队吃饭，时间就是cal(i+k 和 i+h)就可以进行dp转移 
                }
            }
        }

第一次写题解。。不喜轻喷。。也可以直接略过