DP决策优化小结

终于大概学懂了点吧。。。感觉以前全在胡诌


决策单调性

适用于形如 \(dp[i]=min(dp[j])+w(j,i)\ ,\ j\in[1,i)\) 的dp问题。
此形式被称为1D问题。

1.决策点

若 \(dp[i]\) 由 \(dp[j]\) 转移得到,则称 j 是 i 的决策点,记为 \(p[i]=j\)。
决策单调性即对于 \(i\in[1,n]\),决策点单调递增/减。
那于对于j,它能更新一段i,i的取值范围即j的决策区间。

2.四边形不等式

这是决策单调性的基础。
此处均为求最小值,若求最大值自动反号。

式子:\(w(a,c)+w(b,d) \leq w(a,d)+w(b,c)\)
其中 \(a<b<c<d\)。
即交叉<包含。

通过这个,我们可以得到决策单调性。
反证:
若有 \(y<x\) 且 \(p[y]>p[x]\),
则根据最优决策有 \(dp[x]=dp[p[x]]+w(p[x],x)<dp[p[y]]+w(p[y],x)...①\)
同理 \(dp[y]=dp[p[y]]+w(p[y],y)<dp[p[x]]+w(p[x],y)...②\)
则 \(①+②\) 得 \(w(p[x],x)+w(p[y],y)<w(p[x],y)+w(p[y],x)\)
这与我们的四边形不等式矛盾。

关于针对题目的四边形不等式证明,有引理:
\(w(a,b+1)+w(a-1,b)\leq w(a-1,b+1)+w(a,b)\)与原式等价。
此引理证明可以采用归纳法,此处不再赘述。

3.分治决策点

适用于特殊的分层dp,同层之间不相互更新,且相邻层具有决策单调性。

因为决策点单调,我们可以依据决策点划分区间。
那么对于一段区间 \([l,r]\),设已知其决策点区间为 \([pl,pr]\)。
取其中点 mid,先 \(O(n)\) 暴力算出其转移点的决策点 p。
那么必然对于区间 \([1,mid)\) 和 \((mid,r]\),其决策点区间为 \([pl,p]\) 和 \([p,pr]\)。
则我们可以通过分治不断分划区间来减少复杂度。

因为总决策区间是 \(O(n)\) 的,且分治树高为 \(logn\),则总时间复杂度为 \(O(nlogn)\)。

4.二分队列

更为普遍适用于 1D 问题。

由于决策点单调,考虑采用单调队列维护决策点。
如果 \(w(j,i)\) 能够快速计算,我们就可以使用二分在 \(O(logn)\) 的时间内求出相邻两决策点的分界点。

对于队头,只要当前 i 越过其决策区间右端点,就可以出队头。
对于队尾插入,考虑队尾对答案贡献,若 i 能比队尾更快地叉掉次队尾,那么就可以出队尾。实际上是在维护决策分界单调。

这个东西的写法大概有两种:

while(hd<tl&&(find(q[tl-1].x,i)<q[tl-1].k||(find(q[tl-1].x,i)==q[tl-1].k&&dp[i]+calc(i,q[tl-1].k)<=dp[q[tl].x]+calc(q[tl].x,q[tl-1].k)))) tl--;

while(hd<tl&&find(q[tl].x,i)<=q[tl-1].k) tl--;

find函数是寻找分界,calc函数即 \(w(j,i)\)。
一种是判断叉掉次队尾时间快慢,一种是直接比较i和队尾转移到队尾与次队尾分界处谁更优。
明显第二种更快,精度要求更低,也更简单。
要重点注意边界问题。

5.二分栈

没打过,但可以口胡。

还是 1D 问题。
但是这次是后面的决策会被前面赶超。

可以类似维护一个单调栈,每个点存储何时叉掉头上那个点,即决策分界。
那么栈顶就是当前最优决策点。

插入时,先比较i是否优于栈顶,劣则扔掉;优则判断栈顶会不会在叉掉i前被次栈顶叉掉,如果会就一直pop栈顶。

6.广义决策单调性

这已经不是玄妙的范畴了。
还是看cmd的吧,我讲不清楚,而且我也没看懂环上魔法。
cmd的 DP的决策单调性优化总结


斜率优化

理解后其实挺模式化。
适用于特殊的 1D 问题,
形如 \(dp[i]=min(dp[j]+f[i]\times g[j]+a[i]+b[j])\)。

1.斜率式

顾名思义,把式子整成斜率形式。

假设当前转移到 i,决策点 \(j_2>j_1\),且 \(j_2\) 优于 \(j_1\)。
那么 \(dp[j_2]+f[i]\times g[j_2]+a[i]+b[j_2]\leq dp[j_1]+f[i]*g[j_1]+a[i]+b[j_1]\)
转化得 \(f[i]\times (g[j_2]-g[j_1])\leq(dp[j_2]+b[j_2])-(dp[j_1]+b[j_1])\)
令 \(X(j)=g[j]\),\(Y(j)=dp[j]+b[j]\)。
代入移项得 \(f[i]\leq\dfrac{Y(j_2)-Y(j_1)}{X(j_2)-X(j_1)}\)。
这是一个斜率形式。

但是不要高兴得太早,上面默认了 \(X(j_2)-X(j_1)>0\) ,实际上这玩意可能会导致变号。特别是 \(X\) 不具有单调性时,有点令人迷惑。

显而易见的,我们可以通过这个式子决定决策点之间的优劣,并使用单调队列进行维护。而上述式决策点构成的集合在坐标系中表现为上凸;反号则为下凸。
关于这部分的证明,可以看辰星凌的 【学习笔记】动态规划—斜率优化DP,写得非常详细,此处不再赘述。

2.直线式(截距式)

这种方法与形的关系更加密切,更加有助于分析问题。

不对式子做过多变换。
原式整理得 \(-f[i]\times g[j]+(dp[i]-a[i])=dp[j]+b[j]\),
即形如 \(kx+b=y\) 的形式。

可以看到,\(k=-f[i]<0\) 已经确定,而 \(dp[i]_{min}\) 等效于 \(b_{min}\)。
那么我们的目标是找到合适的点 \((g[j],dp[j]+b[j])\) 使过该点且斜率为 \(k\) 的直线截距最小。

显然这玩意应该去维护一个上凸包,用斜率为 \(k\) 的直线去切。
可以发现其实和斜率式的结果并无区别。

3.问题分析

若询问的 \(k\) 与插入的 \(X\) 均单调,那么是有决策单调性的。可以看到队头一定会在某个 \(k\) 被弹出而对后面没有任何贡献。那么可以维护一个单调队列,随 i 递增不断出队头即可。
时间复杂度为 \(O(n)\)。

若询问的 \(k\) 不单调而插入的 \(X\) 单调,那么不能弹出队头,维护的实际上是个单调栈。对于当前 i 查询最优决策点要使用二分,找到第一个满足斜率条件的位置。

若询问的 \(X\) 不单调,不管 \(k\) 是否单调,我们都只能使用数据结构动态维护凸包或者离线算法维护偏序。可以采用平衡树,李超线段树动态维护,或是 CDQ 离线维护,时间复杂度均为 \(O(nlogn)\)。
平衡树因为凸性的原因可以按照 \(X\) 和相邻两点 \(k\) 来 split,避免二分。
CDQ 可以再用 \(O(logn)\) 维护第三维偏序。

4.细节

大多数题目需要先在队列中插入一个零点。
保持出队时保证出队后队列中还有点,最后一个点不能出(其实也出不了,压根没有斜率)。

边界条件需要重点注意。


凸优化/WQS二分

适用于 2D 的分m段极化问题,形如
\(dp[i][s]=min(dp[j][s-1]+w(j,i))\)

1.答案凸性

假设我们已经算出了分 i 段的答案,\(i\in[1,n]\)。
将 \((i,dp[i])\) 在坐标轴上表示出来。

如果这个点集表示出的图形是一个凸包,显然我们可以二分斜率去切这个凸包,直至切到想要的横坐标 m。
则我们只要能够验证答案凸性,就可以解决该问题。

但是我们并没有算出答案,而是需要根据我们的二分的斜率 k 算出答案。
若斜率为 k 的直线经过凸包上一点 j,则有 \(kj+b=dp[j]\)。
转化得 \(b=dp[j]-kj\)。

观察到这等价于将每件物品的价值减去 k 的 1D 问题,或者说每分一段就会有 k 的惩罚。那么就可以采取 1D 方式算出 b,进而用 \(dp[j]=kj+b\) 算出 \(dp[j]\)。

其中 1D 处理过程可以记录每个 \(dp[i]\) 分了多少段,依此决定二分区间。

2.实际问题

大部分时候,上面的答案凸性压根证不出来。
只能想想是否有 \(w(a,c)\leq w(a,b)+w(b+1,c)\),
或者通过感性思考想想是否分段越多越好。

还有一种廉价替代,大概比感性理性一点,称为包含单调。
即 \(w(a-1,b+1)\leq w(a,b)\),满足这个一定会分段越多越好。
就是不知道是咋来的,正确性存疑。

实际上分段问题只要不是太奇怪,一般分段越多就越多/少。

上一篇:22.1 高级函数【JavaScript高级程序设计第三版】


下一篇:计数学习小记