引言

本文暂时只介绍与决策单调性有关的优化。后面会陆续完善其他优化

一、决策单调性优化

1.四边形不等式

[1].定义

设 w [ i ] [ j ] w[i][j] w[i][j]是一个二元函数，若 ∀ a ≤ b ≤ c ≤ d \forall a\le b\le c\le d ∀a≤b≤c≤d满足 w [ a ] [ c ] + w [ b ] [ d ] ≥ w [ a ] [ d ] + w [ b ] [ c ] w[a][c]+w[b][d]\ge w[a][d]+w[b][c] w[a][c]+w[b][d]≥w[a][d]+w[b][c](可以记作交叉大于等于包含)成立，那么称 w [ i ] [ j ] w[i][j] w[i][j]满足四边形不等式的性质。

首先注意到四边形不等式中的大于等于号其实换成小于等于号也是符合定义的，只不过这是另一种对称的情况，这里以大于等于号为例进行接下来的推导。

[2].性质

若 ∀ a < b \forall a<b ∀a<b满足 w [ a ] [ b ] + w [ a + 1 ] [ b + 1 ] ≥ w [ a ] [ b + 1 ] + w [ a + 1 ] [ b ] w[a][b]+w[a+1][b+1]\ge w[a][b+1]+w[a+1][b] w[a][b]+w[a+1][b+1]≥w[a][b+1]+w[a+1][b]成立，那么二元函数 w [ i ] [ j ] w[i][j] w[i][j]满足四边形不等式性质。

证明：根据性质中的条件，那么有：
∀ c + 1 < d \forall c+1<d ∀c+1<d有 w [ c + 1 ] [ d ] + w [ c + 2 ] [ d + 1 ] ≥ w [ c + 1 ] [ d + 1 ] + w [ c + 2 ] [ d ] w[c+1][d]+w[c+2][d+1]\ge w[c+1][d+1]+w[c+2][d] w[c+1][d]+w[c+2][d+1]≥w[c+1][d+1]+w[c+2][d]
又由于 c < d c<d c<d因此有 w [ c ] [ d ] + w [ c + 1 ] [ d + 1 ] ≥ w [ c ] [ d + 1 ] + w [ c + 1 ] [ d ] w[c][d]+w[c+1][d+1]\ge w[c][d+1]+w[c+1][d] w[c][d]+w[c+1][d+1]≥w[c][d+1]+w[c+1][d]。
将上述两式加起来后我们有 w [ c ] [ d ] + w [ c + 2 ] [ d + 1 ] ≥ w [ c ] [ d + 1 ] + w [ c + 2 ] [ d ] w[c][d]+w[c+2][d+1]\ge w[c][d+1]+w[c+2][d] w[c][d]+w[c+2][d+1]≥w[c][d+1]+w[c+2][d]成立。

也就是说在满足性质的条件下我们也满足 ∀ c + 1 < d \forall c+1<d ∀c+1<d，即 c < c + 2 ≤ d < d + 1 c<c+2\le d<d+1 c<c+2≤d<d+1有 w [ c ] [ d ] + w [ c + 2 ] [ d + 1 ] ≥ w [ c ] [ d + 1 ] + w [ c + 2 ] [ d ] w[c][d]+w[c+2][d+1]\ge w[c][d+1]+w[c+2][d] w[c][d]+w[c+2][d+1]≥w[c][d+1]+w[c+2][d]成立。注意到这个范围已经从原来的 a < a + 1 ≤ b < b + 1 a<a+1\le b<b+1 a<a+1≤b<b+1扩大了一些，我们还可以扩大 d d d的范围：

根据 c , d c,d c,d的推论显然对于 ∀ e + 1 < f \forall e+1<f ∀e+1<f满足 e + 1 < f + 1 e+1<f+1 e+1<f+1即满足 e < e + 2 < f + 1 < f + 2 e<e+2< f+1<f+2 e<e+2<f+1<f+2有 w [ e ] [ f + 1 ] + w [ e + 2 ] [ f + 2 ] ≥ w [ e ] [ f + 2 ] + w [ e + 2 ] [ f + 1 ] w[e][f+1]+w[e+2][f+2]\ge w[e][f+2]+w[e+2][f+1] w[e][f+1]+w[e+2][f+2]≥w[e][f+2]+w[e+2][f+1]成立，然后根据 e + 1 < f e+1<f e+1<f我们又有 w [ e ] [ f ] + w [ e + 2 ] [ f + 1 ] ≥ w [ e ] [ f + 1 ] + w [ e + 2 ] [ f ] w[e][f]+w[e+2][f+1]\ge w[e][f+1]+w[e+2][f] w[e][f]+w[e+2][f+1]≥w[e][f+1]+w[e+2][f]，两式相加我们得到 w [ e ] [ f ] + w [ e + 2 ] [ f + 2 ] ≥ w [ e + 2 ] [ f ] + w [ e ] [ f + 2 ] w[e][f]+w[e+2][f+2]\ge w[e+2][f]+w[e][f+2] w[e][f]+w[e+2][f+2]≥w[e+2][f]+w[e][f+2]成立。也就是说 ∀ e + 1 < f \forall e+1<f ∀e+1<f即 e < e + 2 ≤ f < f + 2 e<e+2\le f<f+2 e<e+2≤f<f+2满足等式 w [ e ] [ f ] + w [ e + 2 ] [ f + 2 ] ≥ w [ e + 2 ] [ f ] + w [ e ] [ f + 2 ] w[e][f]+w[e+2][f+2]\ge w[e+2][f]+w[e][f+2] w[e][f]+w[e+2][f+2]≥w[e+2][f]+w[e][f+2]成立，在这一步中我们将范围进一步扩大，从上一步的 c < c + 2 ≤ d < d + 1 c<c+2\le d<d+1 c<c+2≤d<d+1扩大到 e < e + 2 ≤ f < f + 2 e<e+2\le f<f+2 e<e+2≤f<f+2。

利用上述方式我们可以将范围任意扩大，最终我们能够得到 ∀ a ≤ b ≤ c ≤ d \forall a\le b\le c\le d ∀a≤b≤c≤d我们都有 w [ a ] [ c ] + w [ b ] [ d ] ≥ w [ a ] [ d ] + w [ b ] [ c ] w[a][c]+w[b][d]\ge w[a][d]+w[b][c] w[a][c]+w[b][d]≥w[a][d]+w[b][c]成立。

注意到我们最初的假设其实只是 若 ∀ a < b \forall a<b ∀a<b满足 w [ a ] [ b ] + w [ a + 1 ] [ b + 1 ] ≥ w [ a ] [ b + 1 ] + w [ a + 1 ] [ b ] w[a][b]+w[a+1][b+1]\ge w[a][b+1]+w[a+1][b] w[a][b]+w[a+1][b+1]≥w[a][b+1]+w[a+1][b]成立 最终我们却导出了 w [ i ] [ j ] w[i][j] w[i][j]满足四边形不等式的性质，故我们要证明的结论是正确的。根据这个性质我们能够比较轻松的判断一个函数 w [ i ] [ j ] w[i][j] w[i][j]是否满足四边形不等式，此外如果无法直接通过数学表达式判断的话我们还可以打表找规律判断。

2.递推式类型一

[1].递推式定义

定义一个dp方程的递推式满足 d p [ i ] = m a x 0 ≤ j ≤ i { d p [ j ] + w [ j ] [ i ] } dp[i]=max_{0\le j\le i}\{dp[j]+w[j][i]\} dp[i]=max0≤j≤i​{dp[j]+w[j][i]}。(换成 m i n min min其实也行，不过要再按过程推导一下)

[2].最优决策点定义

假设 h [ i ] h[i] h[i]满足 ∀ k ∈ [ 0 , i ] \forall k\in[0,i] ∀k∈[0,i]有 d p [ h [ i ] ] + w [ h [ i ] ] [ i ] ≥ d p [ k ] + w [ k ] [ i ] dp[h[i]]+w[h[i]][i]\ge dp[k]+w[k][i] dp[h[i]]+w[h[i]][i]≥dp[k]+w[k][i]那么我们说 h [ i ] h[i] h[i]是 d p [ i ] dp[i] dp[i]的最优决策点，也就是说 d p [ i ] dp[i] dp[i]其实是由 d p [ h [ i ] ] dp[h[i]] dp[h[i]]转移过来的。

[3].决策单调性定义

若 d p dp dp方程满足 h [ 0 ] ≤ h [ 1 ] ≤ h [ 2 ] ≤ . . . . . h[0]\le h[1]\le h[2]\le ..... h[0]≤h[1]≤h[2]≤.....，我们说 d p dp dp方程的递推性质具备决策单调性。

[4].决策单调性判定条件

假设 w [ i ] [ j ] w[i][j] w[i][j]满足四边形不等式 ∀ a ≤ b ≤ c ≤ d , w [ a ] [ c ] + w [ b ] [ d ] ≥ w [ a ] [ d ] + w [ b ] [ c ] \forall a\le b\le c\le d,w[a][c]+w[b][d]\ge w[a][d]+w[b][c] ∀a≤b≤c≤d,w[a][c]+w[b][d]≥w[a][d]+w[b][c]，那么我们可以断言 d p dp dp方程满足决策单调性。

证明：考虑对于 i i i我们作出最优转移即 d p [ i ] = d p [ h [ i ] ] + w [ h [ i ] ] [ i ] dp[i]=dp[h[i]]+w[h[i]][i] dp[i]=dp[h[i]]+w[h[i]][i]，然后 ∃ k ≤ h [ i ] \exist k\le h[i] ∃k≤h[i]满足 d p [ h [ i ] ] + w [ h [ i ] ] [ i ] ≥ d p [ k ] + w [ k ] [ i ] dp[h[i]]+w[h[i]][i]\ge dp[k]+w[k][i] dp[h[i]]+w[h[i]][i]≥dp[k]+w[k][i]成立，同时对于 ∀ i ′ ≥ i \forall i'\ge i ∀i′≥i有 k ≤ h [ i ] ≤ i ≤ i ′ k\le h[i]\le i\le i' k≤h[i]≤i≤i′成立，又由于 w [ i ] [ j ] w[i][j] w[i][j]满足四边形不等式，因此有 w [ k ] [ i ] + w [ h [ i ] ] [ i ′ ] ≥ w [ k ] [ i ′ ] + w [ h [ i ] ] [ i ] w[k][i]+w[h[i]][i']\ge w[k][i']+w[h[i]][i] w[k][i]+w[h[i]][i′]≥w[k][i′]+w[h[i]][i]成立，将两式相加可以得到 d p [ h [ i ] ] + w [ h [ i ] ] [ i ′ ] ≥ d p [ k ] + w [ k ] [ i ′ ] dp[h[i]]+w[h[i]][i']\ge dp[k]+w[k][i'] dp[h[i]]+w[h[i]][i′]≥dp[k]+w[k][i′]成立，也就是说一定有 h [ i ′ ] ≥ h [ i ] h[i']\ge h[i] h[i′]≥h[i]成立。至此我们证明了 d p dp dp方程具有决策单调性。

[5].利用决策单调性加速dp方程求解

下面介绍两种方法来对dp递推式进行优化，其中法一效率更高，但写法更加复杂，理解起来也更加困难，法二效率较低，但是写法简单，理解起来也相对容易。

<1>.法一：单调队列优化

设置一个队列数组 q [ ] q[] q[]用于维护一堆决策点， h e a d head head作为头指针， t a i l tail tail作为尾指针。
我们的做法是遍历整个 d p dp dp数组从而进行更新，遍历的方式一般可以按下标从小到大，不过在具体题目中会存在差异。
假设现在正在更新 d p [ t ] dp[t] dp[t]，考虑维护这个队列，使得 q [ h e a d + 1 ] q[head+1] q[head+1]恰好为当前的最优决策点，而 q [ h e a d + 2 ∼ t a i l ] q[head+2\sim tail] q[head+2∼tail]记录将来可能成为最优决策点的决策点。

设函数 f x ( i ) = d p [ x ] + w [ x ] [ i ] f_x(i)=dp[x]+w[x][i] fx​(i)=dp[x]+w[x][i]，我们画出 f x − i f_x-i fx​−i图像大致如下所示(注意 f x f_x fx​函数的起始下标一定从 x x x开始，此外这里的图像是上凸的，但是不同题目图像可能会有差异，要具体题目具体分析，不过原理都是相似的)：

其实我们在对 d p [ t ] dp[t] dp[t]进行决策的时候本质上就是找到一个 k ∈ [ 0 , t ] k\in[0,t] k∈[0,t]满足 f k [ t ] f_k[t] fk​[t]最大，大致如下图所示：

根据上图的话我们显然要令 h [ t ] = 1 h[t]=1 h[t]=1，也就是说要保证队头 q [ h e a d + 1 ] = 1 q[head+1]=1 q[head+1]=1才行。然后与其说 q [ ] q[] q[]中储存的是最优决策点，其实不如说 q [ ] q[] q[]中储存的就是如上图所示的一个个函数，当前函数值最大的函数对应的下标其实就是最优决策点。比如当前 f x f_x fx​的值是最大的，那么 x x x就是最优决策点，因此我们不妨将当前最优决策点对应的函数叫做最优决策函数。

现在我们将维护队列的工作分为两个部分，第一部分是维护队头，第二部分是维护队尾。

维护队头： 注意到上图有这样一个特性，那就是如果 f x f_x fx​原来是最优决策函数，但是现在不是最优函数，那么它以后也必不可能成为最优决策函数了。什么意思呢，我们知道我们维护的 q [ h e a d + 1 ] q[head+1] q[head+1]就是当前对于 d p [ t ] dp[t] dp[t]而言的最优决策函数，但是一旦 q [ h e a d + 1 ] q[head+1] q[head+1]对应的函数值小于等于 q [ h e a d + 2 ] q[head+2] q[head+2]对应的函数值的时候，我们说 q [ h e a d + 1 ] q[head+1] q[head+1]对应的函数值在以后也一定小于等于 q [ h e a d + 2 ] q[head+2] q[head+2]对应的函数值，因此它不再具有决策价值， q [ h e a d + 1 ] q[head+1] q[head+1]在以后一定是不可能成为其它 d p dp dp的最优决策点，因此在这种情况下我们 h e a d + + head++ head++即可，也就是需要除去队头。

维护队尾： 每次更新完 d p [ t ] dp[t] dp[t]以后我们还需要将 t t t加入队列，这对应的就是一个新的决策函数 f t f_t ft​，如果 f t f_t ft​在 t t t这一点的值已经大于等于队尾的决策函数的值，那么我们直接除去队尾即可。然后再考虑 t a i l − h e a d ≥ 2 tail-head\ge 2 tail−head≥2的情况，此时我们找到 f q [ t a i l − 1 ] , f q [ t a i l ] f_{q[tail-1]},f_{q[tail]} fq[tail−1]​,fq[tail]​这两个函数，将三个函数 f q [ t a i l − 1 ] , f q [ t a i l ] , f t f_{q[tail-1]},f_{q[tail]},f_{t} fq[tail−1]​,fq[tail]​,ft​简单记作 f 1 , f 2 , f 3 f_1,f_2,f_3 f1​,f2​,f3​，然后将它们之间的关系画出来，大致有两种情况，分别如下图所示：
情况一：

情况二：

我们发现情况二中函数 f 3 f_3 f3​在 c c c点就把 f 2 f_2 f2​给超过了，也就是说 f 2 f_2 f2​将永远没有机会成为最优决策函数，而情况一中 f 2 f_2 f2​在 a − c a-c a−c段显然是有机会成为最优决策函数的。因此对于情况二而言我们需要从队列尾部除去 f 2 f_2 f2​函数。

具体如何判断 f 1 , f 2 , f 3 f_1,f_2,f_3 f1​,f2​,f3​的关系是情况二呢，我们可以考虑二分查找交点 c c c的横坐标，然后判断在 c c c的横坐标的位置是否满足 f 1 ≥ f 2 f_1\ge f_2 f1​≥f2​即可，如果满足那么说明 f 2 f_2 f2​没有利用价值了，可以直接 t a i l − − tail-- tail−−。

通过上述操作我们可以保证整个队列中的函数图像时刻保持一种单调的性质，类似下图所示：

上面的图中每个函数都存在一个阶段可能作为最优决策函数，通过维护队头和队尾我们达到了保证队头时刻是当前所有决策函数最大值的特性。

由于中间涉及二分，故总复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)。

<2>法二：分治法

分治法就比较好理解了，我们考虑 d p [ l ∼ r ] dp[l\sim r] dp[l∼r]的最优决策点假设位于 L ∼ R L\sim R L∼R内，设 m i d = l + r 2 mid=\frac {l+r}2 mid=2l+r​，那么我们暴力遍历 [ L , m i n ( m i d , R ) ] [L,min(mid,R)] [L,min(mid,R)]区间找到最大值来更新 d p [ m i d ] dp[mid] dp[mid]，一旦更新成功，我们假设 h [ m i d ] = k h[mid]=k h[mid]=k，那么我们根据决策单调性立马可以知道 d p [ l ∼ m i d − 1 ] dp[l\sim mid-1] dp[l∼mid−1]的最优决策点一定位于 L ∼ k L\sim k L∼k，同时也可以得到 d p [ m i d + 1 ∼ r ] dp[mid+1\sim r] dp[mid+1∼r]的最优决策点一定位于 k ∼ R k\sim R k∼R，于是递归下去即可。总复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)。

2.递推式类型二