线段树优化 dp？线段树优化 dp！
Solution
题目来源：ABC334F（in 洛谷| in AtCoder）题目大意很清晰就不讲了。
我们发现礼物是固定从 \(1\sim n\) 房间送的，唯一要分讨的地方就是什么时候要回去拿礼物。所以很容易想到二维 dp。
定义 \(f_{i, j}\) 表示圣诞老人从起点出发，到拿着 \(j\) 个礼物去 \(i\) 号房间后送出一个所用最短距离。
首先当 \(j \neq k\) 即礼物没有装满时，直接从上个房间过来更优。所以有 \(f_{i, j} = f_{i - 1, j + 1} + \mathrm{Dis}(i - 1, i)(j < k)\)。其中 \(\mathrm{Dis}(i, j)\) 表示 \(i\) 号房间和 \(j\) 号房间之间的距离。
现在考虑 \(j = k\) 的情况。当我们想拿着最多的礼物去到 \(i\) 号房间时，因为去上一个房间已经用了一个礼物，所以我们不得不回家一趟去把礼物装满。我们在 \(f_{i - 1, (j \in [1, k])}\) 中选一个已耗距离最小的状态，在那个状态的基础上回家拿礼物，再送往当前房间即可。
那么就有了状态转移方程：
其中 \(0\) 号点是家。边界条件是 \(f_{1, k} = \mathrm{Dis}(1, 0)\)。
可是这个 dp 是 \(O(n ^ 2)\) 的，显然无法通过本题。考虑优化。先观察 dp 过程，我们可以发现：\(f_{i, 1\sim k-1}\) 完全可以由 \(f_{i-1, 2\sim k}\) 整体区间加实现，需要特殊对待的 \(f_{i, k}\) 也只需要由 \(f_{i-1, 1\sim k}\)。求区间最小值实现。
那么我们就可以只维护一个一维数组 \(D\) 的一段长度为 \(k\) 的窗口。一开始一维数组最左边只有一个元素 \(D_i = \mathrm{Dis}(1, 0)\)。每次，我们在数组最右端（记为 \(r + 1\)）加上 \(\min_{i = \max(1, r - k + 1)} ^ r D_i\)，然后对区间 \([r - k + 1, r]\) 进行一个区间的加。这样更新操作与跑 \(O(n^2)\) 的 dp 是完全等价的。
答案显然是 \(\min_{j = 1} ^ k f_{n, j} + \mathrm{Dis}(n, 0)= \min_{i = (r_{\max} - k + 1)} ^ {r_\max} D_i + \mathrm{Dis}(n, 0)\)。
区间加区间最小值可以使用线段树维护。时间复杂度 \(O(n\log n)\)。