• 周四. 12月 1st, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

dp优化瞎吹

admin

11月 28, 2021

dp优化瞎吹

众所周知,我们在dp的转移过程中,可以用一些方法,优化它的转移复杂度。

由于我这边的资料不多,并且例题要么很简单,要么很难,所以我学的脑子有点乱,东西也乱,抱歉啊

前言

对于dp的优化,我个人有些浅显的理解,不知恰当不恰当

我感觉它大概就是,我先写一个dp,再想办法把它变得更快。

怎样更快呢?我可以优化状态数,也可以优化转移。

对于状态数的优化,在dp基础那一篇里有些许提到。而这里主要是针对转移的优化。

转移可以怎么优化呢?我可以 打表 观察转移点的规律,减少转移数;也可以用数据结构,直球的加速转移。

数据结构优化

最直白的一种。这种直接对着转移做就行了。

如果转移是一段 前缀/后缀的和/min/max/积/啥别的, 我们可以使用前缀和优化。这种非常傻逼,例题略。

如果转移是一段区间的min/max/啥别的,还要带修改,那估计得上线段树优化。当然,有一种特殊的:我们的区间长成一段滑动窗口,并且求min/max,我们可以使用单调队列优化,少一个log

然后就是,对于 (f_i+…ightarrow f_{i+1})​ 这样的转移,发现它是一个区间平移操作,可以利用平衡树的插入操作支持,因为插入相当于自带一个“让位置”。

以下是例题。

线段树优化:CF833B

很容易写出暴力dp:(f(k,i)) 表示分了 (k) 段,选到 (i) 位置,最大的价值和。

那么 (f(k,i)=max f(k-1,j)+w(j+1,i))(w(l,r)) 表示 ([l,r]) 里面不同种类数。

然后我们发现这个东西可以用pre数组贡献出来:对于 ([j+1,i]) 中的位置,如果它 (prele j) ,那就贡献 (1)

枚举 (k)​ ,然后枚举 (i)​。线段树维护:对于每个 (j)​,当前取 (j)​​ 位置转移,权值 (f(k-1,j)+w(j+1,i))​ 能取到多少。首先用 (f(k-1,*)) 作为权值建一颗数,对于每个新来的 (i),对于 ((pre_i,i]) 区间内的 (j),可以多一个贡献出来,给它权值 (+1)​ 就行。我们发现它很明显可以线段树维护:区间+1,区间求max。

然后就搞一遍,复杂度 (O(nklog n))

平衡树优化:CF809D

就拿LIS的那个dp做,发现是一个区间平移的形式,啪的一下打完平衡树,很快啊,哎,就A掉了

另见:这里,这边主要讲的是做dp的思维方法,更加详细一些

决策单调性

对于 (f_i),我们要选一个 (j<i),使得 (g(j)+w(j,i)) 最优化(可能是min/max)。

(p_i) 表示 (i)​​ 这个位置的最优决策点。如果这个 (p)​ 是递增的,这个就叫 决策单调性

如果有这个性质,咋搞呢?我们可以分治,设 calc(l,r,L,R) 表示,要求区间 ([l,r]) 的dp值,当前的转移位置区间确定在 ([L,R]) 中。设 (mid)(l,r) 中点,暴力找到它的最优位置 (p),然后由决策单调性递归确定左右两边的转移位置,递归调用 calc(l,mid-1,L,p),calc(mid+1,r,p,R) 即可。复杂度一个 (log)

除此之外,有些决策单调性的题目也可以在单调栈上二分。不过复杂度一样,并且适用的范围完全被包含了,所以我没有去学,也不太会。

那如何发现这个性质呢?如果足够聪明,你可以脑子里想到几个东西,然后推一推,很快就可以推出来这个性质。如果你不够聪明,像我一样,就可以使用打表,发现这个 (p)​ 好像增。多造点数据,assert一波,发现确实没问题,诶↑,单调性来了。

我们也可以取观摩一下 FlashHu的博客,然后根据函数的交点数/导数等性质,判断它是否满足决策单调性。

以下是例题。

POI2011

LightningUZ Conductor (幻视)

首先转换为 (pge a_j-a_i+sqrt{|i-j|})。那就变成对于每个 (i),求 (j) 使得后面那一坨最大。把 (j<i)(j>i) 分开做,最后合并一下即可。现考虑 (j<i)

可以用一个dp,(f(i)=maxleft(a_j+sqrt{|i-j|}ight)-a_i)

我们可以用数学方法推式子来证明它的决策单调性,也可以观察打表,发现它的决策单调性。

然后就随便做一波就行了。

CF868F

首先,我们使用理性证明 打表,百度,谷歌 等方法发现了决策单调性。证明详见上面FlashHu的博客。

然后用分治算就行了。

过程中,我们发现,我们需要一个够快的方法来支持区间权值的询问。可以考虑像莫队一样增/减一个位置来移动区间。我们又发现,同一层里面,区间 (l,r) 都是递增的,所以区间移动 不会增加 分治决策单调性的复杂度

斜率优化

这里

四边形不等式

对于一个区间dp,枚举一个中间断点转移的那种,我们可以观察它的最优转移点取在哪。然后有的时候,我们就会发现一个和决策单调性有点类似的性质。设 (p(l,r)) 表示 (l,r) 的转移点,那么: (p(l,r-1)le p(l,r)le p(l+1,r))​。此时我们可以用一个和决策单调性类似的继承转移位置的策略,我们不从 (l) 开始,而是直接从以前确定好的 (p)​ 开始,看哪个点最优。容易证明这个复杂度是均摊 (O(n^2)) 的。

经典例题如石子合并,可以做到 (O(n^2))

如果用另一种算法结合平衡树,可以做到 (O(nlog n))​,我不说是哪个

那么四边形不等式是什么呢?

定义:若二元函数 (f(x,y)) 对于 (lle l’le r’le r),有:(f(l,r)+f(l’,r’)ge f(l,l’)+f(r,r’)),则称 (f) 满足 四边形不等式

若有一个dp,形如:(f(l,r)=w(l,r)+max{(l,k)+f(k+1,r)}),则以下三个命题等价:

  • (f) 满足四边形不等式
  • (w) 满足四边形不等式
  • (f) 的最优转移位置 (p),满足 (p(l,r-1)le p(l,r)le p(l+1,r))

证明:我不会,可以感性理解,领悟它的正确性(

更多例题:我不清楚

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注