洛谷P2157[SDOI2009]-学校食堂

  • \(f[i][j][k]\) 表示在第 \(1 \sim i-1\) 个人已经打完饭的情况下,第 \(i\) 个人以及 \(ta\) 后面的 \(7\) 个人是否打饭的状态为 \(j\),上一个打饭的人是第 \(i + k\) 个人
  • 因为是十进制转二进制,所以二进制的最后一位是表示的是第 \(i\) 个人的状态
  • 且 \(k\) 的取值范围是 \(-8 \le k \le 7\),所以第三维统一加上 \(8\),区间平移。(\(RE\) 的滋味可不好受)
  • \((a ~|~ b) - (a ~\&~ b) = a \oplus b\) (具体过程自己推)
  • 当第 \(i\) 个人打好饭了(即 \(j ~\&~ 1\) 为真)时,此时的状态就等价于 \(f[i + 1][j >> 1][k - 7]\),因为当第 \(i\) 个人也打好饭时,对于第 \(i+1\) 个人来说,就是他前面的人都打好了饭,而上一个打饭的人还是第 \((i + 1) + (k - 1) = i + k\) 个人,所以 \(f[i][j][k + 8]\) 也就等价于 \(f[i + 1][j >> 1][k + 7]\)
  • 进而得到转移方程:
if (j & 1) f[i + 1][j >> 1][k + 7] = min(f[i + 1][j >> 1][k + 7], f[i][j][k]);
  • 若第 \(i\) 个人没打好饭,则可以在第 \(i \sim i + 7\) 个人中选一人打饭,此时就有了忍耐度的限制,因此令 \(lim =\) 当前未打饭的所有人的最大忍受范围
  • 超出 \(lim\) 的人打饭会引起众怒,不合法
  • 可以枚举当前合法却还没打上饭的人,让他们赶紧干饭,我们也好赶紧统计答案,也就是 \(l\) 从 \(0\) 枚举到 \(7\),一旦发现当前点不合法,直接 \(break\)
  • 同时也得注意第一道菜是瞬间完成的,进而得到我们第二种情况下的转移方程:
if (i + k == 0) { //(上一道菜做的是空气)
    f[i][j | (1 << l)][l + 8] = min(f[i][j | (1 << l)][l + 8], f[i][j][k + 8];
} else { //(上一道真做菜了)
    f[i][j | (1 << l)][l + 8] = min(f[i][j | (1 << l)][l + 8], f[i][j][k + 8] + (t[i + k] ^ t[i + l]));
}
  • 自然 \(f[n + 1][0][k] (0 \le k \le 8)\)就是我们答案出现的位置了,为什么是 \(0 \le k \le 8\) 呢,因为最后一个干上饭的人肯定在队中啊 (总不能做菜给幽灵吃吧),所以要保证 \(n + 1 + (k - 8) \le n + 1\),\(k\) 自然而然地就 \(\le 8\) 了
  • 问为什么 \(k \ge 0\) 的,别学了直接退役吧
#include <bits/stdc++.h>

#define MAXN 1100
#define MX 256

using namespace std;

int C, n, t[MAXN], b[MAXN], f[MAXN][MX][20];

int main() {
    scanf("%d", &C);
    while (C--) {
        memset(f, 0x3f, sizeof(f));
        f[1][0][7] = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &t[i], &b[i]);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < MX; j++) {
                for (int k = -8; k <= 7; k++) {
                    if (f[i][j][k + 8] == 0x3f3f3f3f) {
                        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 lim = 2e9;
                        for (int l = 0; l <= 7; l++) {
                            if (!((j >> l) & 1)) {
                                if (i + l > lim) {
                                    break;
                                }
                                lim = min(lim, i + l + b[i + l]);
                                if (i + k) {
                                    f[i][j | (1 << l)][l + 8] = min(f[i][j | (1 << l)][l + 8], f[i][j][k + 8] + (t[i + k] ^ t[i + l]));
                                } else {
                                    f[i][j | (1 << l)][l + 8] = min(f[i][j | (1 << l)][l + 8], f[i][j][k + 8]);
                                }
                            }
                        }
                    }
                }
            }
        }
        int ans = 2e9;
        for (int i = 0; i <= 8; i++) {
            ans = min(ans, f[n + 1][0][i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}
上一篇:getfacl语法2


下一篇:三.Go微服务--令牌桶实现原理