单调队列优化和决策单调性优化

时间:2022-10-01 20:45:24

前言:dp蒟蒻拼命挽救一下dp a....,会围绕三个“形如”来写...但更重要的是本质理解啊qwq

A.单调队列优化:

有时状态转移方程形如f[i][j]=min{f[i-1][k]}+w(i,j),其中l(i,j)<=k<=j,l(i,j)<=l(i,j+1)。 如果两个决策k1,k2满足f[i-1][k1]<=f[i-1][k2]且k1>k2,那么k1出现后k2就没用了。 维护一个队列,按k从小到大存下所有有用的决策,f[i-1][k]是单调上升的。 每次加入新决策时,从队列末尾删去没用的决策。 当队列开头决策的k<l(i,j)时将它删去。(emmmmmmm这个海星,在单调性满足情况下用单调队列留下靠后的且较优的)

B.决策单调性优化:

首先对于所有的疑似决策单调性优化的题,最好是用打表来证明(随便搞个大样例或者后头对拍一下.....一般严谨证明不太现实,当然也可以)这个在打O(N^2+)暴力时顺便记录一下gi就行了(这里gi指是从gi转移到i的)[最好考试都要先打好暴力,然后对着暴力来想a,分析性质]

这里主要介绍两种实现:

1.二分实现:

首先是讲稿上的一些说法:

有时状态转移方程形如f[i]=min{f[j]+w(j,i)},其中j<i。 记g(i)表示f[i]取到最优值时的决策点j,如果g(i)<=g(i+1),我们可以用单调性优化dp。 同样用一个单调队列存下有用的决策,对于相邻两个决策k1<k2,我们二分求出k2比k1优的时间t(k1,k2)。加入一个新决策时,假设新决策为k3,末尾两个决策为k1,k2。如果t(k2,k3)<=t(k1,k2),那么可以删去k2。 转移时如果开头的决策已经不优了就删去它。

接下来补充一点自己理解的具体实现:

首先,对于所以的gi可以先标记为1(0)[视题目而定]默认为全都为从1转移过来的,这里用一个结构体的栈来维护每个单调决策的适用范围。

然后,我们依次考虑往后的单调决策更新,那么对于每个i我们先通过二分已经维护的单调决策的适用范围可以算出f[i](用线段树啥的来刷一遍gi有点太傻了a....)同时由此我们可以得出复杂度为O(nlogn)(因为二分嘛)。

现在我们得到了新的f[i],所以用它来更新以后的,由于单调性,我们可以从后往前扫描栈,这里有两种情况:

(1)如果这个老决策的作用区间的起始位置(即L)仍然不如新决策优,那么我们弹出老决策,将老决策的作用区间整个合并到新决策中,继续往前扫 ;
(2)如果不满足前面的条件,在老决策的作用区间中二分出新决策起作用的起始位置,将老决策分割,新决策入栈,结束扫描过程
 ;

这里每个决策里的二分就是对于当前的m判断f[i]+w[i,m]和f[j]+w[j,m]谁更优,若更优则i的起始范围往前移,否则往后移;

感觉这个二分实现还挺好想的a....(雾)而且适用范围貌似要比分治实现更广一些(听分治实现的时候一脸懵a...)

在这里推荐一道例题(实打代码才有效)

bzoj4709: [Jsoi2011]柠檬 

以及代码(咕咕咕):

 

2.分治实现:

首先依旧是讲稿上的一些说法:

有时状态转移方程形如f[s][i]=min{f[s-1][j]+w(s,j,i)},其中j<i,且g(s,i)<=g(s,i+1)。 如果w(s,j,i)不能很快算出,之前的方法就不再适用了。 假设i的取值范围是[l,r],取m=(l+r)/2。我们可以先求出g(s,m),然后递归处理[l,m-1]和[m+1,r]。

接下来依旧是补充一点自己理解的具体实现:

(咕咕咕)