解决的问题
斜率优化 DP 可以优化以下形式的转移方程:
其中 \(a(i),c(i)\) 表示与 \(i\) 有关的函数,\(X(j),Y(j)\) 表示与 \(j\) 有关的函数,\(L\) 代表一个常量。
在上面的式子中,如果 \(a(i)\times X(j)\) 不存在那么就是单调队列或者线段树优化,其余的东西的存在与否并不重要。
解决办法
考虑如果存在 \(j1,j2\),满足 \(j1<j2\) 且 \(j1\) 劣于 \(j2\)(默认取 \(\min\),也就是 \(F(j1)>F(f2)\),如果是 \(\max\) 反过来就行了)。
就有:
化简得到:
发现上面这个东西和 \(y=kx+b\) 的一次函数很像,那么令 \(k_0=a(i)\) 就有:
移项,然后提取公因式:
不妨设 \(X(j2)>X(j1)\),注意用的时候不等号的方向,那么同除得到:
总结一下,也就是如果上面的式子成立,那么 \(j2\) 比 \(j1\) 优秀。
如果令 \(k_0\gets -k_0\) 那么就和求斜率的式子一模一样了,考虑把 \(X,Y\) 搬到直角坐标系里。
下面只考虑不等式是 \(>\) 的情况。
假设三个决策点分别是 \(A,B,C\),\(AB\) 的斜率是 \(k1\),\(BC\) 的斜率是 \(k2\)。
- 如果 \(k_0>k_1\),那么 \(B\) 比 \(A\) 优。
- 如果 \(k_0>k_2\),那么 \(C\) 比 \(B\) 优。
- 显然根据图像有 \(k1>k2\),也就是 \(B\) 是一个上凸。
有三种情况:
- \(k_0>k_1\wedge k_0>k_2\),那么 \(C\) 优于 \(B,A\)。
- \(k_1>k_0\wedge k_0>k_2\),那么 \(A,C\) 优于 \(B\)。
- \(k_1>k_0\wedge k_2>k_0\),那么 \(A\) 优于 \(B,C\)。
根据上面的分析,得到结论上凸永远都不可能是最优点。
把上凸全部删除之后得到的肯定是一个下凸,也就是这样的东西:
假设下图中的红线是 \(k_0\),那么肉眼可与看出第 \(5\) 个决策点是最优秀的。
因为 \(5\) 要节点之后的 \(k\) 都大于 \(k_0\),前面的都小于 \(k_0\)。
所以说 \(5\) 就是第 \(1\) 个比 \(k_0\) 的斜率大的连线的靠前的决策点。
发现因为是下凸,所以有单调性可以二分。
如果有 \(m\) 个决策点,那么这样二分:
double slope(int i,int j){if(X(j)==X(i)) return Y(j)>=Y(i)?inf:-inf;return 1.0*(Y(j)-Y(i))/(X(j)-X(i));
}
int F(int k0){int l=1,r=top-1,p=inf;while(l<=r){int mid=(l+r)/2;if(slope(mid,mid+1)<k0) l=mid+1,p=mid;else r=mid-1;}if(p==inf) return s[1];return s[p+1];
}
总结
如果是(取 \(\min\) 且 \(X\) 单调递增)或者(取 \(\max\) 且 \(X\) 单调递减)那么维护下凸。
否则,维护上凸。
注意事项
- 尽量避免使用除法,避免精度误差。
- 注意一些情况需要向凸包内加入如 \(\{0,0\}\) 这样的初始值。
- 注意可能 \(X\) 的值一样,需要加一个 \(mdf\) 来扰动以下。
- 在把式子整理的时候 \(c(i)+L\) 其实就是和 \(j\) 无关的东西,不一定要分开。
- 注意是否要保留这样的斜率一样的情况:
补充
对于 \(X\) 不单调的情况,我们就不能进行直接移项,考虑进行一些奇技淫巧进行调整。
我们考虑分治,先处理左区间,然后再用左区间得到的结果处理右区间。
具体的,把左右区间分别递归完之后再归并排序即可。
整体来说就是一个 CDQ 分治,另外也可以使用李超线段树。