复盘｜第318场周赛

对数组执行操作

【原地赋值】按题意模拟，原地操作O(1)空间。

长度为 K 子数组中的最大和

【哈希表 + 滑动窗口】不能每划一次就重新计算一遍会TLE，先把k-1个元素加到窗口里，然后开始滑。

雇佣 K 位工人的总代价

【两个最小堆】读题，找到合适的数据结构，维护一些数字中的最小值、需要去掉最小值、需要加入元素 —→ 堆。如果前后的candidates元素重叠，直接对costs排序取剩余的k个数。代码中，i指向前c的下一个待加入元素，指向后c的前一个待加入元素，必须i ≤ j表示没重叠，如果i > j可以把pre和suf拼起来当作costs。 相当于把一开始就重叠和操作后的重叠的两种情况合在一起。[python切片有拷贝，空间复杂度是O(n)，go是O(1)，当然也可以用itertools.islice实现O(1)，不过不能传入heapify。最后的排序+切片，也可以快速选择求前k小，时间复杂度为O(n)，]

最小移动总距离

【记忆化搜索】用邻项交换法可以证明，对机器人和工厂按照位置从小到大排序，那么每个工厂修复的机器人就是连续的一段了。原问题：n个工厂修m个机器人，子问题：枚举第一个工厂修了x个机器人，转换成n-1个工厂修了m-x个机器人。定义f(i,j)表示用第i个及其右侧的工厂，修理第j个及其右侧的机器人，机器人移动的最小总距离，f(i,j) = min(f(i + 1, k + 1) + cost(i, j , k))，这里cost(i,j,k)表示第i个工厂修复从j到k的机器人，移动距离就是这些机器人到第i个工厂的距离之和。（k-j+1≤limit[i]）

【递推 + 空间压缩】递推比记忆化搜索省空间（递归损耗，以及python内置哈希表实现记忆化，用数组会快点。记忆化搜索通过剪枝优化，递推用数据结构优化转移/压缩空间）。定义f[i] [j] 为前i个工厂修复前j个机器人的最小移动总距离。代码实现时，第一个维度可以像01背包那样优化掉。