洛谷 P11459
标签
分治，Minkowski令 \(cost(r)\) 表示将 \(s_{r - l + 1 \sim r}\) 变成哞叫的代价。有一个显然的 DP，令 \(dp_{i, j}\) 表示前 \(i\) 个字符形成 \(j\) 个哞叫的最小代价。那么 \(dp_{i, j} = \min(dp_{i, j}, dp_{i - L, j - 1} + cost(i))\)，可能可以使用 slope trick 进行优化，但比较复杂。
遇到不会的时候，可以想想想分治。显然跨过分治中心 \(mid\) 的哞叫至多一个，所以可以设计出一个 DP，设 \(dp_{l, r, i, j, c}\) 表示对于区间 \([l, r]\)，最左边的 \(i\) 个和最右边的 \(j\) 个不考虑的情况下的凑出 \(c\) 个哞叫的最小代价。
设左半部分的 DP 数组为 \(L\)，右半边是 \(R\) 那么 \(dp_{l, r, i, j, c} = \min\limits_{x = 0}^{c} \{\min(L_{i, 0, x} + R_{j, c - x}, \min\limits_{l = 1}^{L - 1} \{ L_{i, L - l, x} + R_{l, j, c - x - 1} + cost(mid + l) \}) \}\)
表示没有跨国中间的哞叫，跨过中间的哞叫为右端点为 \(mid + l\)。
这个是一个闵可夫斯基和的形式，也就是两个数组的归并的结果，然后对 \(dp_{l, r, i, j ,x}\) 进行贡献。只需要证明凸性即可。
证明可以从开头讲的那个 DP 出发，归纳的证明。相当于是两个上凸函数每个位置取 min 后的结果，也是一个上凸函数。感性的理解，就是需要的哞叫越多，单次的花费越大。（比较符合直觉。）
时间复杂度：\(O(L^3n \log n)\)
算是一个套路把，对于要求选出 \(k\) 个的题，可以分治后转成 \(k = i + j\) 的形式，然后使用闵可夫斯基和优化，需证明凸性/打表。