题目链接

题意:见原题面。


先写 DP:\(f_i=min(f_j+cal(i,j)\) 这里 cal 不拆开写了... 前缀和减一下减 L 再 P 次幂。

考虑到这个 DP 方程具有严格决策单调性:

证明其实挺简(套)单(路)的,假设不满足,化一化式子可以得到一个\((X+A)^p-(X-Y+A)^p \leq (X)^p+(X-Y)^p\) 的形式,显然不成立。

这里如果这个式子转移的时候 f_i 不与 f 有关,就可以分治优化了,然而不行。

从左向右的计算每个 f_i,发现算出一个后可以更新后面一个后缀区间的决策点,二分出来,然后区间染色维护决策点即可。

其实可以少个 log,扫的时候用个双端结构维护一下即可,详见代码。

需要注意的坑点有两个:

long long 存不下,用 long double 存

long double pow 炸精,手写个 pow 即可。

 


一个非常弱的准退役OIER