热启动（简单版）题解

思路

处理到 $a_i$ 后，刚运行它的 CPU 的最后程序一定是 $a_i$。因此只需记录另一个 CPU 的最后程序，而不必记录两个完整历史。

做法

子任务 1：枚举分配

枚举长度为 $n$ 的二进制串，表示每个程序交给哪个 CPU，直接模拟两个 CPU 的最后程序并取最小值，复杂度 $O(n2^n)$。

子任务 2：两种程序

当 $k\le2$ 时，另一个 CPU 的最后程序只有 $0,1,2$ 三种状态。逐项转移即可在 $O(n)$ 时间完成。

子任务 3：完整 DP

令 $dp_x$ 表示已经处理到 $a_i$，刚使用的 CPU 最后程序为 $a_i$，另一个 CPU 最后程序为 $x$ 的最小耗时。

运行 $a_{i+1}=y$ 时：

• 继续使用当前 CPU，状态 $x$ 不变，按 $a_i=y$ 决定冷热代价；
• 改用另一个 CPU，新状态为 $a_i$，按 $x=y$ 决定冷热代价。

对全部 $x$ 转移，复杂度为 $O(nk)$。

正确性证明

引理 1 上述状态包含决定下一次运行代价所需的全部信息。

证明 下一次代价只取决于所选 CPU 上一次运行的程序；一个 CPU 的最后程序固定为当前 $a_i$，另一个由 $x$ 记录。∎

引理 2 两类转移枚举了运行下一程序的所有选择。

证明 下一程序只能交给刚使用的 CPU 或另一个 CPU，分别对应两类转移，代价按最后程序是否相同精确计算。∎

定理 DP 的最小值等于最优总耗时。

证明 初始状态正确；由引理 1 和引理 2，每一步无遗漏且代价准确。归纳可得所有可行分配及其最小代价均被记录，末尾取最小即为答案。∎

复杂度

满分算法每组时间复杂度 $O(nk)$，空间复杂度 $O(k)$。