P8923

怎么 ARC 还能撞题的？只能说 Kubic 牛逼。 首先显然没法保序回归。考虑用类似于凸壳优化 DP 的做法解决原问题（也就是 P4331）： - 设 $dp_{i,j}$ 表示考虑前 $i$ 位，$x_i=j$ 的最小代价，显然有 $dp_{i,j}=\min_{k\le j}\{dp_{i-1 ......

[题面传送门](https://www.luogu.com.cn/problem/P8923) 这不是保序回归板子吗（ 首先你拿保序回归通法做这个题那是一点前途没有，所以你考虑一点更优秀的方法。 众所周知保序回归 $L_{2k+1}$ 问题可以slope trick。考虑设 $f_{i,j}$ 表示 ......