分组游戏题解

思路

设 $w(l,r)$ 为子数组 $a_l,\ldots,a_r$ 的代价。朴素分组动态规划为

$$dp_{g,r}=\min_{g\le p\le r}\{dp_{g-1,p-1}+w(p,r)\}.$$

小规模可以枚举所有 $k-1$ 个切分位置。中规模按右端点向左扫描，维护每个值当前最左出现位置，即可在 $O(n^2k)$ 时间完成上述转移。

代价函数 $w$ 满足四边形不等式，因此每一层动态规划的最优决策点单调。可以用分治优化：计算区间中点时枚举给定的候选决策范围，再递归处理左右两半。

分治过程中需要快速得到任意移动区间的代价。维护当前区间内每个值的出现位置双端队列。向右加入位置 $i$ 时，若该值已经出现，代价增加 $i-last$；向左加入时增加 $first-i$。删除端点时做相反更新。这样每移动一个端点只需 $O(1)$。

做法

初始化 $dp_{0,0}=0$，其余状态为无穷大。依次计算 $g=1,2,\ldots,k$：

1. 在合法下标区间 $[g,n]$ 上调用分治过程。
2. 对中点 $m$ 枚举决策点 $p$，用当前窗口求出 $w(p,m)$。
3. 记录最优决策点 $q$；左半区间的决策范围缩为左端到 $q$，右半缩为 $q$ 到右端。
4. 完成一层后交换新旧动态规划数组。

最终答案为 $dp_{k,n}$。

复杂度

每层分治枚举与窗口移动的总复杂度为 $O(n\log n)$，总时间复杂度为 $O(kn\log n)$，空间复杂度为 $O(n)$。