【问题求解II-HW6.B】Cache调度

本题摘自 Codeforces 1799D1。你可以点击网站右侧的 Tutorial 查看官方题解 (官方题解从最朴素的时间复杂度为 $O(nk^2)$ 的动态规划讲起，逐步优化，清晰易懂，非常建议同学们仔细阅读)。这里我们给出一个另外的解法，比官方解法更加简洁高效。

我们首先可以发现一个贪心性质。对于某一个类型为 $t$ 的程序来说，如果它只需要花 $hot_t$ 的时间执行，那么情况一定是：在这个程序之前最近的一个类型为 $t$ 的程序在某块 Cache 上 (不妨记为 Cache 0) 执行之后，它们中间的程序都在 Cache 1 上执行，然后当前程序在 Cache 0 上执行。为什么当前程序不可能“继承"更早的 $t$ 类型程序使用的 Cache 呢？假设这种情况发生了，如下图：

在这个例子中，当前的1类型程序“继承”了更早的同类型程序，它们中间还夹着一个1类型程序。那么我们没有道理不把中间的这个1类型程序拉到下面的 Cache 上执行——一方面，这个1类型程序的左右都不是1类型，将它挪下来甚至可能让上面这块 Cache 多命中一次 (虽然图示例子不符合这个情况，1 的左右程序类型不一样)，另一方面，把这个程序拉下来可以让它享受 $hot_1$ 的执行时间。因此这是一笔稳赚不赔的买卖。

我们在这个性质的基础上进行动态规划。为了方便叙述，我们首先约定一些记号：

• 令 $last_i$ 表示在第 $i$ 个程序之前最近的一个和 $i$ 同类型的程序的位置。该数组不难获取，具体细节留给大家思考。
• 令 $sum_{l, r}$ 表示将 $[l+1, r]$ 这个区间里的程序按顺序在同一块 Cache 上执行所需的总时间，注意我们不计算第 $l$ 个程序的执行时间，将第 $l$ 个程序纳入讨论是为了确定第 $l+1$ 个程序能否享受到 Cache hit 的加速。该记号可以通过前缀和实现。

令 $dp(i, 0/1)$ 表示当前看到第 $i$ 个程序，第 $i$ 个程序使用的 Cache 和第 $i-1$ 个程序一样 (用第二维的 1 表示)/不一样 (0) 的情况下，最小的执行时间。令第 $i$ 个程序的类型为 $t$，分以下两种情况讨论：

• 第 $i$ 个程序没有享受到 Cache hit，花了 $cold_t$ 的时间执行：这种情况下我们完全不用在意前面是哪两个程序留在了 Cache 里，因为我们没打算 Cache hit。因此 $$ dp(i, 0) = dp(i, 1) = \min\{dp(i-1, 0), dp(i-1, 1)\} + cold_t $$
• 第 $i$ 个程序享受到了 Cache hit，花了 $hot_t$ 的时间执行：根据我们之前发现的结论，它一定是继承了和它最近的相同类型程序的 Cache，然后中间的其他程序在另一块 Cache 上执行，这里又分两种情况：

  • 上一个同类型的程序是第 $i-1$ 个，则此时满足“和前一个程序使用了同一块 Cache”，因此更新 $dp(i, 1)$： $$ dp(i, 1) = \min\{dp(i - 1, 0), dp(i - 1, 1)\} + hot_t $$

  • 上一个同类型的程序不是第 $i-1$ 个，则此时更新 $dp(i, 0)$: $$ dp(i, 0) = dp(last_i + 1, 0) + sum_{last_i+1, i - 1} + hot_t $$

    注意一个细节：$dp(last_i+1, 0)$ 只能从 0 状态转移来，因为我们要强制 $[last_i + 1, i - 1]$ 的程序换到另一块 Cache 上。在这种情况中，你也可以体会到为什么状态设计中有这么一个看似奇怪的“和前一个程序是否使用同一块 Cache”。

对上述所有情况取 min 即可。你可能会有疑问：第一种情况计算的是不是不太精细，随便放也是有可能命中的？但命中情形下的最优解一定会被第二类情况覆盖到，所以第一种计算的粗糙一些问题不大。第一种情况存在的意义是保证 Cache miss 下达到最小时间的情况被覆盖到 (有点玄妙，请仔细体会)。

最终答案为 $\min\{dp(n, 0), dp(n, 1)\}$，时间复杂度和空间复杂度均为 $O(n+k)$。