Hot Start Up（困难版）题解

思路

处理完 $a_i$ 后，刚运行程序的 CPU 的最后记录必为 $a_i$。因此只需记录另一个 CPU 的最后程序。设 $f_x$ 表示处理完当前前缀、另一个 CPU 最后运行程序为 $x$ 时的最小代价，$x=0$ 表示该 CPU 尚未运行程序。

转移到下一个程序 $v=a_{i+1}$ 时有两种选择。若仍使用刚运行 $a_i$ 的 CPU，所有状态都增加同一个代价；若改用另一个 CPU，新状态的另一个记录变成 $a_i$，而启动代价只取决于原状态 $x$ 是否等于 $v$。

做法

直接枚举所有 $x$ 可以得到二次动态规划。设在转移前所有 $f_x$ 的最小值为 $m$，则切换 CPU 的最优候选为

$$\min\bigl(m+cold_v,\ f_v+hot_v\bigr).$$

这是因为除 $x=v$ 以外的所有状态切换到程序 $v$ 都支付 $cold_v$，只有 $x=v$ 支付 $hot_v$。

不切换 CPU 时，所有状态统一增加

$$\Delta=\begin{cases} hot_v,&a_i=v,\\ cold_v,&a_i\ne v. \end{cases}$$

用一个全局懒加值表示这次统一增加，只维护每个状态扣除懒加后的相对值及其全局最小值。每一步只需查询 $m$ 与 $f_v$，并对状态 $a_i$ 做一次取最小更新，所以每个程序只处理常数次。

初始时第一个程序必须冷启动，设 $f_0=cold_{a_1}$，其余状态为无穷大。处理完整个序列后，全局最小相对值加懒标记就是答案。

第一个子任务可以枚举每个程序选择哪一个 CPU，共 $2^n$ 种分配。第二个子任务使用上述状态但逐次扫描全部 $k+1$ 个状态。满分做法利用统一加法与特殊状态 $v$ 的结构把转移优化为线性。

复杂度

每个测试用例的时间复杂度为 $O(n+k)$，空间复杂度为 $O(k)$。全部测试用例的总时间复杂度为 $O(\sum n+\sum k)$，总空间峰值为 $O(\max k)$。