nfls 集训的作业题。

考虑 dp。设 $f_i$ 表示前 $i$ 个串的最小代价，$s_i$ 为前缀和，则：

$$f_i=\min_{j\in [0,i)} f_j+|s_i-s_j+i-j-L-1|^p$$

然后发现右边的东西关于 $s_i+i-L-1$ 是一个对称的东西，而且二阶导恒非负。这个时候考虑使用二分队列优化决策单调性。

考虑用三元组 $\left\langle j, l, r \right\rangle$ 表示 $l\to r$ 内的最优决策点为 $j$。

遍历 $i:1\to n$，当队首的 $r\lt i$ 的时候先扔掉，然后令 $l=i$。

对于队尾的一些 $\left\langle j,l,r \right\rangle$，如果 $i\to l$ 的决策比 $j\to l$ 的决策更优，根据决策单调性，$[l,r]$ 内的决策都是 $i$ 更优，直接舍弃 $j$，更替为 $i$。

如果我们弹出的过程中遇到了第一个不满足上述条件的 $\left\langle j,l,r \right\rangle$，那么一定存在一个决策点 $p\in [l,r]$，满足 $\forall x\in [l,p]$，$j$ 更优，$\forall x\in [p+1,r]$，$i$ 更优。直接二分出来就行。

时间复杂度均摊 $\mathcal O(n\log n)$。