Slope Trick

定义

本质上是用一个二元组 \((S,f(x))\) 描述由一堆直线构成的分段函数去优化dp，要求这些分段函数满足凸性。其中 \(S\) 是一个可重集，\(f(x)\) 是一个一次函数。

我们定义转折点为斜率在它两侧忽然变化的点，那么 \(S\) 维护的是所有转折点的横坐标，\(f(x)\) 维护的是图像最右边无限延伸出去的直线的方程。考虑到这样无法描述斜率的具体变化，我们规定在一个转折点两侧斜率变化为 \(k\) 就将这个转折点加入 \(S\) \(k\) 次。容易发现这样可以唯一确定满足要求的一个分段函数。

例如 \(f(x)=|x-a|\) 就可以被 \((\{a,a\}, y=x-a)\) 表示。

注意到两个凸性相同的函数相加仍是具有凸性的，而我们发现这样表示函数具有良好的性质：\((S,f(x))+(T,g(x))=(S\cup T, f(x)+g(x))\)，两个函数的和依然可以轻松被表示出来。注意到它要维护的信息只有转折点个数级别，我们可以用它来优化一些dp题。

example

例如：CF713C Sonya and Problem Wihtout a Legend

首先可以让 \(a_i-=i\) 使单调递增变成单调不降。

我们定义dp状态： \(f(i,j)\) 表示只考虑前 \(i\) 个数，所有数都小于 \(j\) 的最小次数， \(g(i,j)\) 表示只考虑前 \(i\) 个数，第 \(i\) 个数恰好等于 \(j\) 的最小次数。可以发现 \(g(i,j)=\min_{k\le j} f(i-1,k) + |a_i-j|\), 显然 \(g\) 是一堆凸函数相加满足凸性。\(f\) 是 \(g\) 的前缀最小值也是下凸的。

我们发现这个转移的代价是一个绝对值，是下凸函数。我们考虑维护由 \((j,f(i,j))\) 构成的一个函数。注意到加一个绝对值函数只会增加两个转折点，可以用之前的方法维护转折点。但是加入转折点之后我们维护的函数从 \((j,f(i,j))\) 变成了 \((j,g(i,j))\)。

这题有良好的性质，\((i,f(i,j))\) 在最后斜率一定会到 \(0\)，\((i,g(i,j))\) 到最后斜率一定会是转到 \(1\)。并且 \(f(i,j)\) 只在最后一部分和 \(g(i,j)\) 不一样。我们只用改一下最后的函数值，移除最大的转折点就可以从 \(g\) 变到 \(f\)。实现只需要一个堆。

输出方案暂时不会，咕咕咕。