假设当前的 DP 方程为

fi=min⁡0≤j−K(i)X(j)+Y(j)}+F(i)

或

fi=max⁡0≤j−K(i)X(j)+Y(j)}+F(i)

其中 F(i)F(i)F(i)、K(i)K(i)K(i) 为关于 iii 的函数，X(j)X(j)X(j)、Y(j)Y(j)Y(j) 为关于 jjj 的函数。

接下来只考虑 fi=min⁡0≤j−K(i)X(j)+Y(j)}+F(i) 的情况，因为另一个与这个相似。

此时，我们设 B(i)B(i)B(i) 为 fi−F(i)f_i - F(i)fi​−F(i)。方程就成为

B(i)=min⁡0≤j−K(i)X(j)+Y(j)}

对于一个一次方程 y=kx+by=kx+by=kx+b，其可以转换为 b=y−kxb=y-kxb=y−kx。

所以说，原方程相当于求过所有满足 0≤j

假设有一条直线 y=K(i)x+by=K(i)x+by=K(i)x+b，从 b=−∞b=-\inftyb=−∞ 开始，不断上移，直到碰到第一个碰到的点 (X(j),Y(j))(X(j),Y(j))(X(j),Y(j))，答案 B(i)=bB(i) = bB(i)=b。

这个问题可以使用凸包解决。

即求出所有满足 0≤j

（图片引用至 OI - WIKI）

然后求出凸包上斜率为 K(i)K(i)K(i) 的直线的切点。

我们可以用平衡树，二分，CDQCDQCDQ 等方法求出切点。

平衡树时间复杂度 O(nlog⁡n)O(n\log n)O(nlogn)，CDQCDQCDQ 时间复杂度 O(nlog⁡2n)O(n\log^2 n)O(nlog2n)，二分 O(nlog⁡n)O(n\log n)O(nlogn)。

如果函数 K(i)K(i)K(i) 满足单调性，则可以用单调队列解决，之后假设 K(i)K(i)K(i) 单调递增。（单调递减则类似）

单调队列储存了凸包上的一些节点 P0,P1,P2,...P_0, P_1,P_2,...P0​,P1​,P2​,...。

若当前斜率改变为 K(i)K(i)K(i)，我们每次判断单调队列中前两个点 P0,P1P_0,P_1P0​,P1​ 组成线段的斜率是否小于 K(i)K(i)K(i)。若小于，则删除 P0P_0P0​，重复刚才的步骤。反之，切点为 P0P_0P0​。

求出切点后，我们对应可以求出 B(i)B(i)B(i)，也可以求出 fif_ifi​。

这时，我们根据 fif_ifi​ 计算出 X(i)X(i)X(i) 和 Y(i)Y(i)Y(i)，在图中添加点 (X(i),Y(i))(X(i),Y(i))(X(i),Y(i))。

维护一个动态凸包即可。