二维决策单调性

对于形如 $d_{i,j}=\min\limits_{k=0}^{i-1} \Big( d_{k,j-1}+w(k+1,i) \Big)$ 的方程，我们尝试记录 $f_{i,j}$ 代表 $d_{i,j}$ 的最优转移点（$k$ 变量），如果有 $f_{i,j-1} \leq f_{i,j} \leq f_{i+1,j}$，那么就是经典的四边形不等式优化，复杂度为 $O(n^2)$，证明此处略（在"四边形不等式相关.md"里有）。

但是，如果只有 $f_{i,j} \leq f_{i+1,j}$，那么就不能用四边形不等式优化了，需要用分治的方式优化。

具体地，我们从小到大枚举 $j$，然后转移所有的 $d_{i,j}$。

定义分治函数dp(l,r,jl,jr)代表我们要转移所有的 $d_{i,j}$（$l \leq i \leq r$），并且保证所有在本次分治转移范围内的 $d_{i,j}$ 的转移点 $f_{i,j}$ 都在 $[jl,jr]$ 内。

我们可以先求出 $[l,r]$ 的中点 $mid$，然后转移 $d_{mid,j}$：暴力枚举转移点 $k$（当然，要在 $[jl,jr]$ 内）进行转移，并递归dp(l,mid-1,jl,最终转移点)和dp(mid+1,r,最终转移点,jr)。

该算法复杂度为 $O(n^2 \log n)$，证明：

首先，枚举 $j$ 的复杂度 $O(n)$。

其次，只看 $[jl,jr]$，$[jl,jr]$ 在递归的过程中就形成了个线段树的类似结构，只不过单层内可能有部分重叠位置，而且划分点（上面说的“最终转移点”）可能不是中点，不过无关紧要。

然后，再看 $[l,r]$，$[l,r]$ 在递归过程中也形成了类似于线段树的结构，并且易证这个递归树深度是不会超过 $\log n$ 的。

有了深度的保证，而且一层内的 $[jl,jr]$ 区间长度和最多只有 $O(n)$ 级别，所以一次分治的复杂度就是 $O(n \log n)$。

一共 $n$ 次分治，总复杂度为 $O(n^2 \log n)$。

一维决策单调性

如果是一维的转移方程 $d_i=\min\limits_{j=0}^{i-1} \Big( d_j+w(j+1,i) \Big)$，如果也满足决策单调性（记 $d_i$ 的最优转移点为 $f_i$，那么就是说满足 $f_i \leq f_{i+1}$），那么如何优化呢，可以用决策二分栈（说是用栈，但我看其他人大多都写的是队列）。

下面统一设 $g(j,i)=d_j+w(j+1,i)$，并设 $c(x,y)$ 代表 $g(x,\dots)$ 大于等于 $g(y,\dots)$ 的最小下标，即 $c(x,y)$ 是满足 $g(x,p) \geq g(y,p)$ 的最小 $p$，满足单调性，可以二分实现。

这里说一下 $c(x,y)$ 的二段性证明，就是决策单调性有一个显然的推论，就是如果 $g(x,\dots)$ 在某一刻超过（大于等于）了另外一个 $g(y,\dots)$，且 $x<y$，那么 $g(y,\dots)$ 就不可能再反超（大于等于）$g(x,\dots)$ 了。

（下述做法为假）

我们用一个队列来维护若干个三元组 $[l,r,x]$，代表说照目前看来，$[l,r]$ 内的 $d$ 值都是从点 $x$ 转移最优。

设当前要转移 $d_i$：

  • 首先，如果仍然满足 $g(队头,i) \geq g(队头后面一个元素,i)$（队头较劣），那么弹出队头。
  • 其次，如果队头的管辖范围仍然不包括 $i$（队头的 $[l,r]$ 不包含当前的 $i$），那么弹出队头。
  • 拿队头的 $x$ 来转移 $d_i$。
  • 然后，不断弹出队尾，找到 $g(i,\dots)$ 超过或等于 $g(队尾的x,\dots)$ 的最小下标（易证满足单调性，所以可以用二分来实现）$k$，然后弹出队尾，插入 $[原本队尾的l,k-1,原本队尾的x]$（如果这个三元组的区间为空或者已经无用，那么就不用插入了）和 $[k,n,i]$。

我们用一个队列 $q$（注意，这里的队列是手写队列）来维护若干个转移点，同时设 $k_i=c(q_i,q_{i+1})$。

然后，就可以转移了：（设当前要转移 $d_i$，当前队列的第一个元素下标为 $h$，最后一个元素下标为 $t$）

  • 首先，只要队列大小大于等于 $2$ 且满足条件 $k_h \leq i$（$g(q_h,i)$ 已经大于 $g(q_{h+1},i)$ 了，即前者已经比后者要劣了，并且后面不可能反转局面了），那么弹出队首。
  • 其次，拿 $q_h$ 作为 $d_i$ 的转移点。
  • 然后，只要队列大小大于等于 $2$ 且满足条件 $k_{t-1} \geq c(q_t,i)$（这个条件可以自己画图理解），那么弹出队尾。
  • 最后，将 $i$ 加入队尾并更新 $k$ 数组即可。