四边形不等式
决策单调
即对于dp方程\(f[i]=min/max(f[j]+w(j+1,i))\),设\(f[i]\)从\(pre[i]\)转移,有$\forall\ i>j,pre[i] \le pre[j] $
写出\(pre[]\)就是大概这种效果:
111111224444444446666
可以观察到决策单增,那么对于有序表,可以想到利用二分或分治等\(O(logn)\)的算法来优化转移,从而达到\(O(nlogn)\)的时间复杂度
一个重要的证明决策单调的方法就是四边形不等式
(当然,考场上可以感性分析或打个表)
二分+栈
由于决策单调,故相同决策点都是相连的,可以通过二分+栈来维护这些区间
我们反向考虑:分析一个点\(i\)最多能更新到那些点,顺序枚举\(i\)
那么就在二分找第一个从\(i\)转移能够最优的点,往后的区间都是以\(i\)转移为优
当然,如果区间\(i\)完全覆盖了前面的某个区间\(j\)(在\(j\)左端点仍是决策\(i\)更优),就从栈中弹出\(j\)
注意:这种方法要求转移要高效,即w(j,i)要支持预处理或本身较快
分治
挺新的思路
由于决策单调,\(pre[i]\)随\(i\)单调而单调,用类二分的思路
设\(Solve(l,r,sl,sr,k)\)为划分第k段,当前处理\(f[l]\)~\(f[r]\),它们可能从\(f[sl]\)~\(f[sr]\)转移
取区间\(mid\),如果\(f[mid]\)从\(f[sm]\)转移,那么\(f[l]\)~\(f[mid]\)就是从\(f[sl]\)~\(f[sm]\)转移,\(f[mid]\)~\(f[r]\)就是从\(f[sm]\)~\(f[sr]\)转移
出现子问题,支持分治
分治的一个优势在于:贡献区间连续(从\([sl,sr]\)到\([sl,sm]\),\([sm,sr]\)),这意味着即使贡献难以预处理,也可以通过莫队优化,使得贡献计算时间正确
标签:pre,sr,决策,sm,sl,优化,单调 From: https://www.cnblogs.com/zhone-lb/p/18522181